[cf-767D]Cartons of milk

Cartons of milk

题意

每天喝$k$瓶牛奶，每瓶牛奶都有$s$的保质日期，现在我有$n$瓶牛奶，去商场最多可以买多少瓶牛奶。

条件是每天都要喝$k$瓶牛奶，在最有情况下所有牛奶都不会过期。

题解

贪心，反正所有牛奶的贡献都是1，所以保质期越后面的越好。

计算能买多少瓶就是从第一天开始遍历，能买到就买对应的期限的牛奶。

+1： 中间一个变量爆了int

+1: 有两个变量$n,m$，sort的时候用了$n$，应该用$m$。

ac代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n,m,k;
const int maxn = 1e6+10;
const int maxm = 1e7+10;
int vis[maxm];
int mx[maxm];
struct node{
    int id;
    int val;
    bool operator<(const node &x)const{
        return val>x.val;
    }
}a[maxn];
int main(){
#ifdef LOCAL
    freopen("3.in","r",stdin);
#endif
    scanf("%d%d%d",&n,&m,&k);
    bool flag = false;
    rep(i,0,n){
        int x;scanf("%d",&x);
        vis[x]++;
    }
    rep(i,0,m){
        int x;scanf("%d",&x);
        mx[x]++;
        a[i].val = x; a[i].id = i+1;
    }
    sort(a,a+m);
    int ans = 0;
    ll  now = k;
    rep(i,0,maxm){
        if(vis[i] > now){
            flag = true;
            break;
        }else{
            int temp = min(now-vis[i],(ll)mx[i]);
            int t = vis[i] + temp;
            ans += temp;
            now += k-t;
        }
    }
    if(flag) puts("-1");
    else{
        printf("%d\n",ans);
        rep(i,0,ans){
            printf("%d ",a[i].id);
        }
        puts("");
    }
    
    return 0;
}