本文主要是介绍Gadgets for dollars and pounds CodeForces - 609D，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
二分结束日期mid 第mid天肯定是要消费的 但当天可能不是最适合消费得日子 所以尽量少花钱 就用美元或英镑买最便宜的东西 然后找出从1到mid间美元与英镑价值最低的两天 看能不能买够k件
两种物品某一种数量为零的判断写错了 又是同样的原因 好难受...
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 0x3f3f3f3f3f3f3f3fstruct node1
{int id;ll val;
};struct node2
{int id;int day;
};node1 per1[200010],per2[200010];
node2 ans[200010];
ll num1[200010],num2[200010];
ll s;
int n,m,k,m1,m2,g1,g2,d1,d2;bool cmp(node1 n1,node1 n2)
{return n1.val<n2.val;
}bool judge(int lim)
{ll sum,minn1,minn2;int i,j,p1,p2,cnt;//printf("***%d***\n",lim);minn1=N,minn2=N;for(i=1;i<=lim;i++){if(minn1>num1[i]){minn1=num1[i];p1=i;}if(minn2>num2[i]){minn2=num2[i];p2=i;}}sum=s;if(m1>0&&m2>0){if(per1[1].val*num1[lim]<per2[1].val*num2[lim]){if(sum<per1[1].val*num1[lim]) return false;sum-=per1[1].val*num1[lim];i=2,j=1;}else{if(sum<per2[1].val*num2[lim]) return false;sum-=per2[1].val*num2[lim];i=1,j=2;}}else if(m1>0){if(sum<per1[1].val*num1[lim]) return false;sum-=per1[1].val*num1[lim];i=2,j=1;}else{if(sum<per2[1].val*num2[lim]) return false;sum-=per2[1].val*num2[lim];i=1,j=2;}cnt=1;if(cnt==k){g1=i-1,g2=j-1,d1=p1,d2=p2;return true;}for(;i<=m1&&j<=m2;){if(per1[i].val*num1[p1]<per2[j].val*num2[p2]){//printf("#1 *%lld %lld*\n",sum,per1[i].val*num1[p1]);if(sum>=per1[i].val*num1[p1]){sum-=per1[i].val*num1[p1];cnt++;if(cnt==k){g1=i,g2=j-1,d1=p1,d2=p2;return true;}}else return false;i++;}else{//printf("#2 *%lld %lld*\n",sum,per2[j].val*num2[p2]);if(sum>=per2[j].val*num2[p2]){sum-=per2[j].val*num2[p2];cnt++;if(cnt==k){g1=i-1,g2=j,d1=p1,d2=p2;return true;}}else return false;j++;}}while(i<=m1){if(sum>=per1[i].val*num1[p1]){sum-=per1[i].val*num1[p1];cnt++;if(cnt==k){g1=i,g2=j-1,d1=p1,d2=p2;return true;}}else return false;i++;}while(j<=m2){if(sum>=per2[j].val*num2[p2]){sum-=per2[j].val*num2[p2];cnt++;if(cnt==k){g1=i-1,g2=j,d1=p1,d2=p2;return true;}}else return false;j++;}return false;
}void solve()
{int l,r,mid,res,i;l=1,r=n,res=-1;while(l<=r){mid=(l+r)/2;if(judge(mid)){r=mid-1;res=mid;}else{l=mid+1;}}printf("%d\n",res);if(res!=-1){for(i=1;i<=g1;i++){printf("%d %d\n",per1[i].id,d1);//if(per1[i].id==0) printf("*#1 %d %d %d %d*\n",g1,g2,m1,m2);}for(i=1;i<=g2;i++){printf("%d %d\n",per2[i].id,d2);//if(per2[i].id==0) printf("*#2 %d %d %d %d*\n",g1,g2,m1,m2);}}return;
}int main()
{ll val;int i,j,tp;while(scanf("%d%d%d%lld",&n,&m,&k,&s)!=EOF){for(i=1;i<=n;i++){scanf("%lld",&num1[i]);}for(i=1;i<=n;i++){scanf("%lld",&num2[i]);}m1=0,m2=0;for(i=1;i<=m;i++){scanf("%d%lld",&tp,&val);if(tp==1){m1++;per1[m1].id=i;per1[m1].val=val;}else{m2++;per2[m2].id=i;per2[m2].val=val;}}sort(per1+1,per1+m1+1,cmp);sort(per2+1,per2+m2+1,cmp);solve();}return 0;
}这篇关于Gadgets for dollars and pounds CodeForces - 609D的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
