首页 > 代码库 > CodeForces 767D Cartons of milk

CodeForces 767D Cartons of milk

二分,排序。

首先感觉题意有问题,什么叫假设今天不喝......

将$f$从小到大排序,$s$也从小到大排序,肯定是期日期大的先买,因此可以对$s$进行二分,然后验证。

#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<ctime>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0);void File(){    freopen("D:\\in.txt","r",stdin);    freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){    char c = getchar();    x = 0;    while(!isdigit(c)) c = getchar();    while(isdigit(c))    {        x = x * 10 + c - 0;        c = getchar();    }}int n,m,k;int f[1000010];struct X{    int g,id;}s[1000010];int t[2000010],sz;bool cmp(X a ,X b){    return a.g<b.g;}bool check(int x){    sz=0; int f1=1,f2=x;    while(1)    {        if(f1==n+1&&f2==m+1) break;        if(f1<=n&&f2<=m)        {            if(f[f1]<s[f2].g) sz++, t[sz]=f[f1], f1++;            else sz++, t[sz]=s[f2].g, f2++;        }        else if(f1<=n) sz++, t[sz]=f[f1], f1++;        else if(f2<=m) sz++, t[sz]=s[f2].g, f2++;    }    for(int b=1;;b++)    {        for(int j=(b-1)*k+1;j<=min(sz,b*k);j++)        {            if(t[j]<b-1) return 0;        }        if(b*k>=sz) break;    }    return 1;}int main(){    scanf("%d%d%d",&n,&m,&k);    for(int i=1;i<=n;i++) scanf("%d",&f[i]);    for(int i=1;i<=m;i++) scanf("%d",&s[i].g), s[i].id=i;    sort(f+1,f+1+n);    sort(s+1,s+1+m,cmp);    bool fail=0;    for(int b=1;;b++)    {        for(int j=(b-1)*k+1;j<=min(n,b*k);j++)        {            if(f[j]<b-1) fail=1;        }        if(b*k>=n) break;    }    if(fail)    {        printf("-1\n");        return 0;    }    int L=1,R=m,pos=-1;    while(L<=R)    {        int mid=(L+R)/2;        if(check(mid)) pos=mid,R=mid-1;        else L=mid+1;    }    if(pos==-1)    {        printf("0\n");        return 0;    }    printf("%d\n",m-pos+1);    for(int i=pos;i<=m;i++) printf("%d ",s[i].id);    printf("\n");    return 0;}

 

CodeForces 767D Cartons of milk