2020.0913组队训练赛 问题 J: Keep it Cool

J：保持凉爽
时间限制：2秒 内存限制： 128 MB 特别法官
译文描述
随着学期工作量的增加，您将获得在实验室中向冰箱中添加苏打水的任务。冰箱有s个插槽，每个插槽可容纳d瓶苏打水，并且您要添加n个新的苏打水瓶。当前冰箱中的苏打水既冷又好，但是新的苏打水却不然，需要在冰箱中冷却一会儿，直到可以饮用为止。
您只能从前面重新装满冰箱，因此在理想的世界中，您将首先取出冰箱中当前所有的苏打水，然后放入n个新的苏打水，然后将旧的和冷的苏打水放在新的冰箱前。那些。但是在理想的世界中，您也不会参加两次考试和完成作业截止日期。您只是太忙而无法完成所有这些工作。
取而代之的是，您只需要将新瓶子放在冰箱的前面，并希望最好。但是，您仍然可以聪明地将新的汽水放入哪个插槽中。每次 学生来汽水时，他们都会从冰箱中一个均匀随机的非空插槽的前面取一个汽水 。您决定将新瓶添加到冰箱中，以使从冰箱中拿走苏打水的所有接下来的m个学生都能得到一个冷水壶的可能性最大化 。
输入
输入的第一行包含四个整数n，m，s和d（1≤n，m，s，d≤100），新的汽水瓶数量，要优化的学生数量，冰箱中的插槽数量，和每个插槽的容量。然后，一行包含s个整数c1，…。。。，cs（每个i为0≤ci≤d），其中ci是当前冰箱插槽i中的汽水瓶数。
您可能会认为冰箱中所有n个新瓶子都有可用空间。
输出
如果接下来的所有m个学生都有机会得到一个冷水壶，则输出s个整数， 描述n个汽水瓶的重新装满方案，以最大程度地防止这种情况发生。
这些s整数的第i个表示在冰箱中插槽i的前面放置了多少新瓶 。如果有多个最佳补充方案，请输出其中任何一种。否则，如果 接下来的所有m个学生都不可能得到冷苏打，则输出“不可能”。
样例输入 复制
5 3 3 4
0 1 4
样例输出 复制
2 3 0

题意如上。
思路：
尽可能把的往冰水少的地方放满即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+15;
typedef long long ll;
ll c[N],vis[N];
struct node{
ll v,id;
}a[N];
bool cmp(node a,node b)
{
    if(a.v==b.v)
        return a.id<b.id;
    return a.v<b.v;
}
int main()
{
    ll n,m,s,d,sum=0;
    cin>>n>>m>>s>>d;
    for(int i=1;i<=s;i++)
    {
        cin>>c[i];
        a[i].v=c[i];
        a[i].id=i;
        sum+=c[i];
    }
    sort(a+1,a+1+s,cmp);
    for(int i=1;i<=s;i++)
    {
        ll v=d-a[i].v;
        if(n>=v)
        {
            vis[a[i].id]=v;
        }
        else
        {
            vis[a[i].id]=n;
        }
        n-=v;
        if(n<=0)
        {
            ll os=0;
            for(int j=i+1;j<=s;j++)
            {
                os+=a[j].v;
            }
            if(os<m)
            {
                cout<<"impossible"<<endl;
                return 0;
            }
            break;
        }
    }
    for(int i=1;i<=s;i++)
    {
        cout<<vis[i]<<" ";
    }
    cout<<endl;
    return 0;
}

本文地址：https://blog.csdn.net/qq_43559193/article/details/108566158