题解：CF767D Cartons of milk

· · 题解

题意

Olya 每天喝 k 盒牛奶。冰箱现有 n 盒牛奶，商店有 m 盒牛奶，每盒有各自的保质期。他优先喝最快过期的牛奶。只有当牛奶过期（保质期 < 0）时才会丢弃。

问她最多能买多少盒商店的牛奶，才能保证所有牛奶都被喝完且不丢弃？若现有牛奶已无法喝完，输出 -1。

分析

发现合法情况判定是：每个 x，满足保质期小于 x 的个数小于等于 (x+1) \times k。

在这里可以判断掉 -1 的情况。

那么用一个桶和前缀和，也就是每个 (i+1) \times k-cnt_i 要大于零，来存储，10^7 是可以存的下的。

以后的 cnt 都是 (i+1) \times k-cnt_i 的形式。

for(int i=1,x;i<=n;i++)
    cin>>x,cnt[x]++,mx=max(mx,x);
......
for(int i=1;i<=mx;i++)
    cnt[i]+=cnt[i-1];
for(int i=0;i<=mx;i++)
    cnt[i]=(i+1)*k-cnt[i];

考虑加入商店的牛奶。

每加一个 x 那么 cnt_x 到 cnt_{mx} 都会减一。

那么加入的条件就是 \min^{mx}_{i=x} cnt_i 要大于 1。

那么考虑加入的顺序：

我选择从大到小加，这样考虑：

前者和后者都已经加了 k 个数，发现前者的最小值明显小于后者，感性理解：前者对后面都有影响，但后者对前面的没有影响。

貌似已经解决了吗？

其实当你写的时候，会先 MLE 再 TLE 最后 WA。

先给出我的 MLE 代码 ::::info[代码]

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define File(x) (freopen(x".in","r",stdin),freopen(x".out","w",stdout))
#define Filein(x) (freopen(x".in","r",stdin))
const int N=1e7+5,M=50,mod=1e9+7,inf=1e14;
int n,m,k;
int cnt[N];
vector<int>f[N];
int mx=0;
vector<int>ans;
signed main(){
    cin>>n>>m>>k;
    for(int i=1,x;i<=n;i++)
        cin>>x,cnt[x]++,mx=max(mx,x);
    for(int i=1,x;i<=m;i++)
        cin>>x,f[x].push_back(i),mx=max(mx,x);
    for(int i=1;i<=mx;i++)
        cnt[i]+=cnt[i-1];
    for(int i=0;i<=mx;i++)
        cnt[i]=(i+1)*k-cnt[i];
    int mi=inf;
    for(int i=mx;i>=0;i--){
        mi=min(mi,cnt[i]);
        if(mi<0)return puts("-1");
        for(int j=0;j<min(mi,(int)f[i].size());j++)
            ans.push_back(f[i][j]);
        mi-=min(mi,(int)f[i].size());
    }
    sort(ans.begin(),ans.end());
    cout<<ans.size()<<"\n";
    for(auto i:ans)
        cout<<i<<' ';
    return 0;
}
/*
*/

:::: 问题出在 vector<int>f[N]; 这个空间太大了。

回答：我们用排序加指针可以解决。

这个是 TLE 代码。 ::::info[代码]

#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define File(x) (freopen(x".in","r",stdin),freopen(x".out","w",stdout))
#define Filein(x) (freopen(x".in","r",stdin))
const int N=1e7+5,M=50,mod=1e9+7,inf=1e14;
int n,m,k;
int cnt[N];
int mx=0;
vector<int>ans;
vector<pair<int,int>>v;
signed main(){
    cin>>n>>m>>k;
    for(int i=1,x;i<=n;i++)
        cin>>x,cnt[x]++,mx=max(mx,x);
    for(int i=1,x;i<=m;i++)
        cin>>x,v.push_back({x,i}),mx=max(mx,x);
    sort(v.begin(),v.end());
    for(int i=1;i<=mx;i++)
        cnt[i]+=cnt[i-1];
    for(int i=0;i<=mx;i++)
        cnt[i]=(i+1)*k-cnt[i];
    int mi=inf,now=v.size()-1;
    for(int i=mx;i>=0;i--){
        mi=min(mi,cnt[i]);
        if(mi<0)return puts("-1");
        while(now>=0&&v[now].first>i)now--;
        if(now==-1)continue;
        while(now>=0&&mi>0&&v[now].first==i)ans.push_back(v[now].second),now--,mi--;
    }
    sort(ans.begin(),ans.end());
    cout<<ans.size()<<"\n";
    for(auto i:ans)
        cout<<i<<' ';
    return 0;
}

:::: 发现用快读就可以解决了。

最后 WA 是 long long 问题。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define File(x) (freopen(x".in","r",stdin),freopen(x".out","w",stdout))
#define Filein(x) (freopen(x".in","r",stdin))
const int N=1e7+5,M=50,mod=1e9+7,inf=1e14;
inline int read(){int x=0,f=1;char ch=getchar ();while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar ();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0',ch=getchar ();}return x*f;}
int n,m,k;
int cnt[N];
int mx=0;
vector<int>ans;
vector<pair<int,int>>v;
signed main(){
    n=read(),m=read(),k=read();
    for(int i=1,x;i<=n;i++)
        x=read(),cnt[x]++,mx=max(mx,x);
    for(int i=1,x;i<=m;i++)
        x=read(),v.push_back({x,i}),mx=max(mx,x);
    sort(v.begin(),v.end());
    for(int i=1;i<=mx;i++)
        cnt[i]+=cnt[i-1];
    for(int i=0;i<=mx;i++)
        cnt[i]=(i+1)*k-cnt[i];
    int mi=inf,now=v.size()-1;
    for(int i=mx;i>=0;i--){
        mi=min(mi,cnt[i]);
        if(mi<0)return puts("-1");
        while(now>=0&&v[now].first>i)now--;
        if(now==-1)continue;
        while(now>=0&&mi>0&&v[now].first==i)ans.push_back(v[now].second),now--,mi--;
    }
    sort(ans.begin(),ans.end());
    cout<<ans.size()<<"\n";
    for(auto i:ans)
        cout<<i<<' ';
    return 0;
}