D. Gadgets for dollars and pounds
题目连接：
http://www.codeforces.com/contest/609/problem/C
Description
Nura wants to buy k gadgets. She has only s burles for that. She can buy each gadget for dollars or for pounds. So each gadget is selling only for some type of currency. The type of currency and the cost in that currency are not changing.
Nura can buy gadgets for n days. For each day you know the exchange rates of dollar and pound, so you know the cost of conversion burles to dollars or to pounds.
Each day (from 1 to n) Nura can buy some gadgets by current exchange rate. Each day she can buy any gadgets she wants, but each gadget can be bought no more than once during n days.
Help Nura to find the minimum day index when she will have k gadgets. Nura always pays with burles, which are converted according to the exchange rate of the purchase day. Nura can't buy dollars or pounds, she always stores only burles. Gadgets are numbered with integers from 1 to m in order of their appearing in input.
Input
First line contains four integers n, m, k, s (1 ≤ n ≤ 2·105, 1 ≤ k ≤ m ≤ 2·105, 1 ≤ s ≤ 109) — number of days, total number and required number of gadgets, number of burles Nura has.
Second line contains n integers ai (1 ≤ ai ≤ 106) — the cost of one dollar in burles on i-th day.
Third line contains n integers bi (1 ≤ bi ≤ 106) — the cost of one pound in burles on i-th day.
Each of the next m lines contains two integers ti, ci (1 ≤ ti ≤ 2, 1 ≤ ci ≤ 106) — type of the gadget and it's cost. For the gadgets of the first type cost is specified in dollars. For the gadgets of the second type cost is specified in pounds.
Output
If Nura can't buy k gadgets print the only line with the number -1.
Otherwise the first line should contain integer d — the minimum day index, when Nura will have k gadgets. On each of the next k lines print two integers qi, di — the number of gadget and the day gadget should be bought. All values qi should be different, but the values di can coincide (so Nura can buy several gadgets at one day). The days are numbered from 1 to n.
In case there are multiple possible solutions, print any of them.
Sample Input
5 4 2 2
1 2 3 2 1
3 2 1 2 3
1 1
2 1
1 2
2 2
Sample Output
3
1 1
2 3
Hint
题意
有n天，一共有m个物品，你需要买k个，你身上有s元人民币。每一天，人民币兑换美元的价格为a[i]，兑换英镑的价格为b[i]。
购买第i种物品，必须要用c[i]块t[i]货币来购买。然后问你最少多少天之内，可以买够t个物品，并且输出哪一天买哪一个物品。
题解：
二分答案。二分天数，很显然我们在这一个范围内，我们在这个范围内兑换美元和英镑最便宜的时候购买，物品则是兑换钱的时候买，然后check花费是否大于s就好了。
代码
#include<bits/stdc++.h>
using namespace std;
inline long long read()
{
long long x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
#define maxn 200005
int n,m,k;
int s;
int Mia[maxn],Mib[maxn];
int a[maxn],b[maxn];
long long suma[maxn],sumb[maxn];
int pm1[maxn],pm2[maxn];
vector<pair<int,int> > c1,c2;
int check(int mid)
{
long long mi = 1e18;
int top = min(k,(int)c1.size()-1);
for(int i=0;i<=top;i++)
{
int i1 = i;
int i2 = k-i;
if(i2>=c2.size())continue;
mi = min(mi,1LL*suma[i1]*Mia[mid]+1LL*sumb[i2]*Mib[mid]);
}
if(mi>s)return 0;
return 1;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&k,&s);
Mia[0]=1e18;Mib[0]=1e18;
for(int i=1;i<=n;i++)
{
a[i]=read();
Mia[i]=min(a[i],Mia[i-1]);
if(a[i]>=Mia[i-1])pm1[i]=pm1[i-1];
else pm1[i]=i;
}
for(int i=1;i<=n;i++)
{
b[i]=read();
Mib[i]=min(b[i],Mib[i-1]);
if(b[i]>=Mib[i-1])pm2[i]=pm2[i-1];
else pm2[i]=i;
}
Mia[0]=0;Mib[0]=0;
for(int i=1;i<=m;i++)
{
int t,c;
t=read(),c=read();
if(t==1)c1.push_back(make_pair(c,i));
else c2.push_back(make_pair(c,i));
}
c1.push_back(make_pair(0,0));
c2.push_back(make_pair(0,0));
sort(c1.begin(),c1.end());
sort(c2.begin(),c2.end());
for(int i=1;i<c1.size();i++)
suma[i]=c1[i].first+suma[i-1];
for(int i=0;i<c2.size();i++)
sumb[i]=c2[i].first+sumb[i-1];
int l = 1,r = n+1;
while(l<=r)
{
int mid = (l+r)/2;
if(check(mid))r=mid-1;
else l=mid+1;
}
if(l>=n+1)return puts("-1");
printf("%d\n",l);
long long mi = 1e18;
int top = min(k,(int)c1.size()-1);
for(int i=0;i<=top;i++)
{
int i1 = i;
int i2 = k-i;
if(i2>=c2.size())continue;
mi = min(mi,1LL*suma[i1]*Mia[l]+1LL*sumb[i2]*Mib[l]);
}
for(int i=0;i<=top;i++)
{
int i1 = i;
int i2 = k-i;
if(i2>=c2.size())continue;
if(suma[i1]*Mia[l]+sumb[i2]*Mib[l]==mi)
{
for(int j=1;j<=i1;j++)
printf("%d %d\n",c1[j].second,pm1[l]);
for(int j=1;j<=i2;j++)
printf("%d %d\n",c2[j].second,pm2[l]);
return 0;
}
}
}