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输入】

【样例2输入】

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

【样例1输出】

【样例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;
}