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样商品 和方案
样例输入
input
Copy
5 4 2 2 1 2 3 2 1 3 2 1 2 3 1 1 2 1 1 2 2 2
output
Copy
3 1 1 2 3
input
Copy
4 3 2 200 69 70 71 72 104 105 106 107 1 1 2 2 1 2
output
Copy
-1
input
Copy
4 3 1 1000000000 900000 910000 940000 990000 990000 999000 999900 999990 1 87654 2 76543 1 65432
output
Copy
-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
分析：暴力枚举天数就会超时，首先我们要知道如果第k天能买完东西，那么k-1天肯定也能买完东西，所以它符合一个上升的子序列，所以我们二分枚举答案天数，对于商品的花费，我们可以对齐贪心排序（注意要记录商品序号，因为最后要输出），花费小的在钱买你，然后用两个前缀和来记录前i个商品的最小美元和英镑花费，在二分判断条件时，看他的钱是否足够就行，，输出结果即可。
一份java超时代码，但这个思想C++能过，估计Java的输入输出的原因，回来我改改做做
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Main {static final long mod=1000000007;static final int N=1000007;static day[] d=new day[N];static ArrayList<goods> listd=new ArrayList<goods>();static ArrayList<goods> listp=new ArrayList<goods>();static Long[] sumd=new Long[N];static Long[] sump=new Long[N];static int n,m,k;static long s;static int dnum;static int pnum;static int dday;static int pday;public static void main(String args[])throws IOException {Scanner in = new Scanner(System.in);n=in.nextInt();m=in.nextInt();k=in.nextInt();s=in.nextLong();for(int i=1;i<=n;i++){d[i]=new day();d[i].a=in.nextInt();}for(int i=1;i<=n;i++){d[i].b=in.nextInt();}for(int i=1;i<=m;i++){int op=in.nextInt(); Long x=in.nextLong();if(op==1){listd.add(new goods(x,i));}elselistp.add(new goods(x,i)); }Collections.sort(listd, new Comparator<goods>(){public int compare(goods a, goods b) {return (int)(a.cost-b.cost);} });sumd[0]=(long) 0;sumd[1]=listd.get(0).cost;for(int i=1;i<listd.size();i++){sumd[i+1]=sumd[i]+listd.get(i).cost;}Collections.sort(listd, new Comparator<goods>(){public int compare(goods a, goods b) {return (int)(a.cost-b.cost);} });sump[0]=(long) 0;sump[1]=listp.get(0).cost;for(int i=1;i<listp.size();i++){sump[i+1]=sump[i]+listp.get(i).cost;}int l=1,r=n;while(l<r){int mid=(l+r)>>1;//System.out.println(mid);if(cal(mid)==1){r=mid;}else{l=mid+1;}}if(l==n){System.out.println(-1);}else{System.out.println(l);for(int i=0;i<dnum;i++){System.out.println(listd.get(i).id+" "+dday); }for(int i=0;i<pnum;i++){System.out.println(listp.get(i).id+" "+pday);}}}private static int cal(int mid) {int min1=(1<<30),min2=(1<<30);int pd = 0,pp = 0;for(int i=1;i<=mid;i++){if(min1>d[i].a){min1=d[i].a;pd=i;}if(min2>d[i].b){min2=d[i].b;pp=i;}}long sum1=0,sum2=0;for(int i=0;i<=listd.size();i++){int j=k-i;if(j>listp.size()||j<0) continue;//System.out.println(min1+" "+min2);if(sumd[i]*min1+sump[j]*min2<=s){dnum=i;pnum=j;dday=pd;pday=pp;return 1;}}return 0;}}
class goods
{long cost;int id;public goods() {}public goods(long cost, int id) {this.cost = cost;this.id = id;}}
class day
{public int a,b;public day(int a, int b) {this.a = a;this.b = b;}public day() {// TODO 自动生成的构造函数存根}public int getA() {return a;}public void setA(int a) {this.a = a;}public int getB() {return b;}public void setB(int b) {this.b = b;}
}