欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Gadgets for dollars and pounds(分治+贪心)

程序员文章站 2022-05-21 23:22:07
...

Gadgets for dollars and pounds
总时间限制: 2000ms 内存限制: 65536kB
描述
一个人手上有s卢布,他要在n天内买m样东西中的k样.
有两种支付方式,每个物品有一种支付方式,要么用美元,要么用英镑。每天有不同的支付方式代价,即换取一美元或英镑,需要付出x[i]卢布的代价。
要求:最早完成买k样东西的天数。如果无法完成任务,输出-1
一种商品只能购买一次,但是一天可以买多种商品
输入
第1行:n, m, k, s
第2行:n个整数,表示多少卢布换一美元
第3行:n个整数,表示多少卢布换一英镑
接下来是m行,每行2个整数,表示每样东西用什么货币结账(1是美元,2是英镑),以及要多少那种外币
输出
输出最短到第几天买完k样商品
样例输入
【样例1输入】

5 4 2 2
1 2 3 2 1
3 2 1 2 3
1 1
2 1
1 2
2 2

【样例2输入】

4 3 1 1000000000
900000 910000 940000 990000
990000 999000 999900 999990
1 87654
2 76543
1 65432
样例输出

【样例1输出】

3

【样例2输出】

-1

提示
【数据规模】
1 ≤ n ≤ 2·10^5 , 1 ≤ k ≤ m ≤ 2·10^5 , 1 ≤ s ≤ 10^9
1 ≤ ai, bi  ≤ 10^6
1 ≤ t  ≤ 2, 1 ≤ c  ≤ 10^6

思路点拔:首先要明确一点,若第i天就能买齐k件商品,那么在低i+1天也能买齐k件商品,所以本题答案具有单调性,也就是数,本题可以采用二分答案的方法来确定结果,在买这k件商品时,就需要用到贪心,贪心策略为:让价格最低的先买,注意,本题是卢布数乘以汇率,而不是英镑/美元来乘以汇率,思路就这样简单,上代码!

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=200005,INF=0x3f3f3f3f; 
//注意:0x3f3f3f3f是int类型里的一个极大值,但它比INT_MAX小
long long m,n,k,s,ans;
long long a[maxn],b[maxn];
struct node//定义结构体记录每件商品的信息就比较方便
{
    long long node,need,styw;  
//need记录商品价格,node表示用另一种货币需要的钱数styw记录商品需要那种货币买
}c[maxn];
bool cmp(const node &x,const node &y) //按价格从小到大排序
{
    return x.need<y.need;
}
bool check(int x)
{
    long long mind=INF,minp=INF;
    for(int i=1;i<=x;i++)
    {
        mind=min(mind,a[i]); //找出最小的美元汇率
        minp=min(minp,b[i]); //找出最小的英镑汇率
    }
    for(int i=1;i<=m;i++)
    {
        if(c[i].styw==1) //卢布换美元
            c[i].need=c[i].node*mind;
        else //卢布换英镑
            c[i].need=c[i].node*minp;
    }
    sort(c+1,c+m+1,cmp);//排序
    long long SUM=0; 
    //SUM记录要买的商品的总钱数,注意这里的SUM写大写是因为要避免关键词的问题
    for(int i=1;i<=k;i++)
    {
        SUM+=c[i].need; //排好序后,将要买的k件商品的价格加和
    }
    if(SUM<=s) //如果能买下来,就返回真
    {
        return 1;
    }
    else //否则说明不能买,就返回假
    {
        return 0;
    }
} 
int main()
{ 
    scanf("%lld %lld %lld %lld",&n,&m,&k,&s); 
    for(int i=1;i<=n;i++) //输入几卢布等于1美元
    {
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;i++) //输入几卢布等于1英镑
    {
        scanf("%lld",&b[i]);
    }
    for(int i=1;i<=m;i++) //输入一件商品需要用什么货币,以及需要用多少
    {
        long long p,q;
        scanf("%lld %lld",&p,&q);
        c[i].styw=p; //记录每件商品用什么样的货币买
        c[i].node=q; //node记录每件商品要用多少其他货币
    }
    long long l=0,r=n;
    while(l<=r) //二分结果
    {
        long long mid=(l+r)/2; //每次都二分
        if(check(mid)) 
        //说明二分出来的结果是正确的,就将mid的值赋给ans,修改右边界
        {
            ans=mid;
            r=mid-1;
        }
        else//否则说明还不对,就修改左边界
        {
            l=mid+1;
        }
    }
    if(ans>0) //如果ans大于0,就输出ans就是本题答案
    {
        printf("%lld\n",ans);
    }
    else //否则就输出-1
    {
        printf("-1\n");
    }
    return 0;
}
相关标签: 贪心 分治