D. Cartons of milk

time limit per test

Olya likes milk very much. She drinks k cartons of milk each day if she has at leastk 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 aren 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 arem 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.

In the first line there are three integers n,m, k (1?≤?n,?m?≤?10⁶,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 integersf₁,?f₂,?...,?f_n (0?≤?f_i?≤?10⁷) — 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, a0 expiration date means it must be drunk today, 1 — no later than tomorrow, etc.

In the third line there are m integers s₁,?s₂,?...,?s_m (0?≤?s_i?≤?10⁷) — expiration dates of the cartons in the shop in a similar format.

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 exactlyx 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 with1). Numbers should not repeat, but can be in arbitrary order. If there are multiple correct answers, print any of them.

3 6 21 0 12 0 2 0 0 2Output
31 2 3Input
3 1 20 0 01Output
-1Input
2 1 20 10Output
11 Note
In the first example k?=?2 and Olya has three cartons with expiry dates0, 1 and 1 (they expire today, tomorrow and tomorrow), and the shop has 3 cartons with expiry date 0 and 3 cartons with expiry date 2. Olya can buy three cartons, for example, one with the expiry date0 and two with expiry date 2.
In the second example all three cartons Olya owns expire today and it means she would have to throw packets away regardless of whether she buys an extra one or not.
In the third example Olya would drink k?=?2 cartons today (one she alreay has in her fridge and one from the shop) and the remaining one tomorrow.
題目大意：
主人公很喜歡喝牛奶，每天會喝K盒，如果不足K盒，就會將所有擁有的都喝了。
不傻的人都知道，牛奶過期了之后肯定就不能喝了，那就只能扔掉。
現在冰箱中有N盒牛奶，超市中有M盒牛奶，如果冰箱中的牛奶喝不完就有浪費的情況出現，輸出-1，否則輸出能夠在超時中購買的牛奶數量的最大值。
并且輸出可以購買的牛奶的編號。
思路：
1、首先我們將冰箱中的牛奶按照到期時間按照從小到大排序，很顯然我們希望先喝到期時間早的，才能更多的避免浪費。
接下來O（n）暴力判斷一下這些牛奶是否都能喝完，如果能，繼續進行，否則輸出-1.
2、接下來我們按照到期時間從大到小排序，很明顯，我們希望購買的牛奶肯定是越晚到期越好。
接下來考慮到這樣一點：購買的牛奶越多，越有可能要浪費掉，所以我們知道這里有一個單調性，我們考慮二分購買的牛奶數量。
對于二分出來的中間值mid，我們暴力處理一次判斷能否將這N+mid盒牛奶都喝完，如果可以，增加購買數量，否則減少購買數量。
過程維護最后一次可行方案數，輸出即可。
Ac代碼（搓比代碼底層優化沒做好，卡邊界1900+ms過的）：
#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;struct node{    int date,pos;}b[1000700];int a[1000700];int c[2007000];int output[2000700];int n,m,k;int cmp(node a,node b){    return a.date>b.date;}int judge(int a[],int n){    int day=0;    int cnt=0;    for(int i=0;i<n;i++)    {        if(day>a[i])return 0;        cnt++;        if(cnt==k)        {            cnt=0;            day++;        }    }    return 1;}int Slove(int mid){    int tot=0;    for(int i=0;i<n;i++)c[tot++]=a[i];    for(int i=0;i<=mid;i++)c[tot++]=b[i].date;    sort(c,c+tot);    if(judge(c,tot)==1)    {        for(int i=0;i<=mid;i++)        {            output[i]=b[i].pos;        }        return 1;    }    else return 0;}int main(){    while(~scanf("%d%d%d",&n,&m,&k))    {        for(int i=0;i<n;i++)scanf("%d",&a[i]);        for(int i=0;i<m;i++)scanf("%d",&b[i].date),b[i].pos=i+1;        sort(a,a+n);sort(b,b+m,cmp);        if(judge(a,n)==0)        {            printf("-1/n");            continue;        }        int ans=-1;        int l=0;        int r=m-1;        while(r-l>=0)        {            int mid=(l+r)/2;            if(Slove(mid)==1)            {                l=mid+1;                ans=mid;            }            else            {                r=mid-1;            }        }        printf("%d/n",ans+1);        for(int i=0;i<ans+1;i++)        {            printf("%d ",output[i]);        }        printf("/n");    }}