【Codeforces Round #398 (Div. 2)】Codeforces 767D Cartons of milk

本文主要是介绍【Codeforces Round #398 (Div. 2)】Codeforces 767D Cartons of milk，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Olya likes milk very much. She drinks k cartons of milk each day if
she has at least k and drinks all of them if she doesn’t. But there’s
an issue — expiration dates. Each carton has a date after which you
can’t drink it (you still can drink it exactly at the date written on
the carton). Due to this, if Olya’s fridge contains a carton past its
expiry date, she throws it away. Olya hates throwing out cartons, so
when she drinks a carton, she chooses the one which expires the
fastest. It’s easy to understand that this strategy minimizes the
amount of cartons thrown out and lets her avoid it if it’s even
possible. Milk. Best before: 20.02.2017. The main issue Olya has is
the one of buying new cartons. Currently, there are n cartons of milk
in Olya’s fridge, for each one an expiration date is known (how soon
does it expire, measured in days). In the shop that Olya visited there
are m cartons, and the expiration date is known for each of those
cartons as well. Find the maximum number of cartons Olya can buy so
that she wouldn’t have to throw away any cartons. Assume that Olya
drank no cartons today. Input In the first line there are three
integers n, m, k (1 ≤ n, m ≤ 106, 1 ≤ k ≤ n + m) — the amount of
cartons in Olya’s fridge, the amount of cartons in the shop and the
number of cartons Olya drinks each day. In the second line there are n
integers f1, f2, …, fn (0 ≤ fi ≤ 107) — expiration dates of the
cartons in Olya’s fridge. The expiration date is expressed by the
number of days the drinking of this carton can be delayed. For
example, a 0 expiration date means it must be drunk today, 1 — no
later than tomorrow, etc. In the third line there are m integers
s1, s2, …, sm (0 ≤ si ≤ 107) — expiration dates of the cartons in
the shop in a similar format. Output If there’s no way for Olya to
drink the cartons she already has in her fridge, print -1. Otherwise,
in the first line print the maximum number x of cartons which Olya can
buy so that she wouldn’t have to throw a carton away. The next line
should contain exactly x integers — the numbers of the cartons that
should be bought (cartons are numbered in an order in which they are
written in the input, starting with 1). Numbers should not repeat, but
can be in arbitrary order. If there are multiple correct answers,
print any of them.

把已有的和可选的分别排序，最后选择的一定是截止日期最晚的一段。
二分答案，判定的时候贪心地每天从两个数组的头开始取。
因为每次最多取 $O(n)$ 次，复杂度 $O(n\log n)$ 。
hack的时候还看到有很多人用并查集，不知道是怎么做的。

#include<cstdio>
#include<algorithm>
using namespace std;
int rd()
{int x=0;char c=getchar();while (c<'0'||c>'9'){x=x*10+c-'0';c=getchar();}return x;
}
struct milk
{int x,num;bool operator < (const milk &mm) const{return x<mm.x;}
}b[1000010];
int a[1000010],n,m,k;
bool ok(int p2)
{int p1=1,now=0;while (p1<=n||p2<=m){if ((p1<=n&&a[p1]<now)||(p2<=m&&b[p2].x<now)) return 0;for (int i=1;i<=k;i++)if (p1<=n&&(p2>m||a[p1]<b[p2].x)) p1++;else p2++;now++;}return 1;
}
int main()
{int l,r,mid;scanf("%d%d%d",&n,&m,&k);for (int i=1;i<=n;i++) scanf("%d",&a[i]);for (int i=1;i<=m;i++){scanf("%d",&b[i].x);b[i].num=i;}sort(a+1,a+n+1);sort(b+1,b+m+1);if (!ok(m+1)){printf("-1\n");return 0;}l=1;r=m+1;while (l<r){mid=(l+r)/2;if (ok(mid)) r=mid;else l=mid+1;}printf("%d\n",m-l+1);for (int i=l;i<=m;i++) printf("%d%c",b[i].num,i==m?'\n':' ');
}