【codeforces 767D】Cartons of milk

【题目链接】:http://codeforces.com/problemset/problem/767/D

【题意】



每个牛奶都有最晚可以喝的时间;

每天喝K瓶牛奶;

你有n瓶牛奶->已知每个牛奶的期限;

然后商店里面有m瓶牛奶；->已知每个牛奶的期限;

然后问你最多能再从商店里买几瓶牛奶;

使得你买的这些牛奶都不会因为过期而被扔掉;

或者你原本的n瓶牛奶都不能做到则输出-1

【题解】



首先肯定喝的顺序是先喝马上就要过期的

->所以原有的n瓶升序排;

然后买的话,肯定是买晚过期的;

所以商店里的m瓶降序排;

然后就是二分答案;

二分x表示买几瓶;->买最晚的x瓶;

然后O(N+X)判断可不可以喝完.

判断的时候没必要把新加的X个再加进去;

直接用类似归并排序的方式看看哪个小就先喝哪个就好;

(两个数组嘛)



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define ps push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%lld",&x)

#define ref(x) scanf("%lf",&x)

typedef pair<int, int> pii;

typedef pair<LL, LL> pll;

const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };

const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };

const double pi = acos(-1.0);

const int N = 2e6 + 100;

struct abc

{

    int day, id;

};

int n, m, k, num, f[N];

map <int, int> extra;

map <int, int> dic;

abc s[N];

bool cmp1(abc a, abc b)

{

    return a.day > b.day;

}

bool check(int x)

{

    int R = x,now = k,day = 0,i = 1;

    while (i <= n)

    {

        if (R == 0 || f[i] < s[R].day)

        {

            if (day > f[i]) return false;

            now--;

            i++;

        }

        else

        {

            if (day > s[R].day) return false;

            R--;

            now--;

        }

        if (now == 0) now = k,day++;

    }

    rep2(i, R, 1)

    {

        if (day > s[i].day)

            return false;

        now--;

        if (now == 0) day++, now = k;

    }

    return true;

}

int main()

{

    //freopen("F:\\rush.txt", "r", stdin);

    rei(n), rei(m), rei(k);

    rep1(i, 1, n)

        rei(f[i]);

    rep1(i, 1, m)

        rei(s[i].day), s[i].id = i;

    sort(f + 1, f + 1 + n);

    sort(s + 1, s + 1 + m, cmp1);

    if (!check(0))

    {

        return puts("-1"), 0;

    }

    int l = 1, r = m, ans = 0;

    while (l <= r)

    {

        int mid = (l + r) >> 1;

        if (check(mid))

        {

            ans = mid, l = mid + 1;

        }

        else

        {

            r = mid - 1;

        }

    }

    printf("%d\n", ans);

    rep1(i, 1, ans)

        printf("%d ", s[i].id);

    puts("");

    //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);

    return 0;

}