CodeForces 609D Gadgets for dollars and pounds

二分天数+验证

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std; const int maxn=+;
int n,m,k;
long long s;
long long a[maxn],b[maxn],c[maxn];
int t[maxn];
long long A[maxn],B[maxn];
int preA[maxn],preB[maxn];
struct Tmp
{
int id;
long long val;
int day;
} tmp[maxn]; bool cmp(const Tmp&a,const Tmp&b)
{
return a.val<b.val;
} int main()
{
scanf("%d%d%d%lld",&n,&m,&k,&s);
for(int i=; i<=n; i++) scanf("%lld",&a[i]);
for(int i=; i<=n; i++) scanf("%lld",&b[i]);
for(int i=; i<=m; i++) scanf("%d%lld",&t[i],&c[i]); A[]=a[];
preA[]=;
for(int i=; i<=n; i++)
{
A[i]=min(A[i-],a[i]);
if(A[i-]<=a[i]) preA[i]=preA[i-];
else preA[i]=i;
} B[]=b[];
preB[]=;
for(int i=; i<=n; i++)
{
B[i]=min(B[i-],b[i]);
if(B[i-]<=b[i]) preB[i]=preB[i-];
else preB[i]=i;
} int l=,r=n;
int mid;
int ansDay=-;
while(l<=r)
{
mid=(l+r)/;
for(int i=; i<=m; i++)
{
tmp[i].id=i;
if(t[i]==) tmp[i].val=A[mid]*c[i];
else tmp[i].val=B[mid]*c[i];
}
sort(tmp+,tmp++m,cmp);
long long sum=;
for(int i=; i<=k; i++) sum=sum+tmp[i].val;
if(sum<=s)
{
ansDay=mid;
r=mid-;
}
else l=mid+;
}
printf("%d\n",ansDay);
if(ansDay!=-)
{
for(int i=; i<=m; i++)
{
tmp[i].id=i;
if(t[i]==) tmp[i].val=A[mid]*c[i];
else tmp[i].val=B[mid]*c[i]; if(t[i]==) tmp[i].day=preA[ansDay];
else tmp[i].day=preB[ansDay];
}
sort(tmp+,tmp++m,cmp);
for(int i=; i<=k; i++)
printf("%d %d\n",tmp[i].id,tmp[i].day);
}
return ;
}
上一篇:Spring面试题复习(一)


下一篇:[jzoj]3777.最短路(shortest)