题目链接：http://codeforces.com/contest/767/problem/D
D比C水系列。
将商店里面的牛奶按照保质期升序排序(显然优先买保质期久的）考虑二分答案，然后再将整个序列归并排序，贪心的检测答案是否正确即可。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 2001000 10 #define llg int 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 12 llg n,m,a[maxn],b[maxn],c[maxn],ans,tail,k; 13 14 inline llg getint() 15 { 16 llg res=0,fh=1;char ch=getchar(); 17 while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); 18 if(ch=='-')fh=-1,ch=getchar(); 19 while(ch<='9'&&ch>='0')res=res*10+ch-'0',ch=getchar(); 20 return res*fh; 21 } 22 23 struct node 24 { 25 llg val,wz; 26 }e[maxn]; 27 28 bool cmp(llg a,llg b){return a>b;} 29 30 bool cmpp(const node&a,const node&b){return a.val>b.val;} 31 32 inline bool check(llg r2) 33 { 34 llg r1=n; 35 llg w1=1,w2=1; tail=0; 36 while (w1<=r1 || w2<=r2) 37 { 38 if (w1>r1) c[++tail]=b[w2],w2++; 39 else if (w2>r2) c[++tail]=a[w1],w1++; 40 else if (a[w1]>b[w2]) 41 { 42 c[++tail]=a[w1],w1++; 43 } 44 else 45 { 46 c[++tail]=b[w2],w2++; 47 } 48 } 49 llg x=tail+1,t=0; 50 while (1) 51 { 52 for (llg i=1;i<=k;i++) 53 { 54 x--; 55 if (x<=0) return 1; 56 if (c[x]<t) return 0; 57 } 58 t++; 59 } 60 return 1; 61 } 62 63 int main() 64 { 65 yyj("D"); 66 cin>>n>>m>>k; 67 for (llg i=1;i<=n;i++) scanf("%d",&a[i]); 68 sort(a+1,a+n+1,cmp); 69 for (llg i=1;i<=m;i++) 70 { 71 scanf("%d",&b[i]); 72 e[i].val=b[i],e[i].wz=i; 73 } 74 sort(b+1,b+m+1,cmp); 75 sort(e+1,e+m+1,cmpp); 76 llg l=0,r=m,mid; 77 ans=-1; 78 while (l<=r) 79 { 80 mid=(l+r)>>1; 81 if (check(mid)) {ans=mid,l=mid+1;}else r=mid-1; 82 } 83 cout<<ans<<endl; 84 for (llg i=1;i<=ans;i++) printf("%d ",e[i].wz); 85 return 0; 86 }