题解：P13422 [COCI 2019/2020 #4] Pod starim krovovima

[题目传送门](https://www.luogu.com.cn/problem/P13422)

## 题目大意
有 $N$ 个玻璃杯，每个杯子有当前液体量 $T_i$ 和容量 $Z_i$。通过在杯子间倒液体（每次可倒任意整数升，但是不能溢出），问最多能让多少个杯子变空，并输出一种可行的最终液体分布方案。

## 题目思路

想要让空杯子的数量尽量多，就要让尽可能多的液体聚集到尽可能少的杯子里。我们可以用贪心算法做这道题。

首先，我们按杯子的容量对杯子进行排序。

然后，依次选择未选的杯子中容量最大的杯子，直到所有液体都可以被装进已选的杯子中，剩下的杯子就是最终可以变空的杯子。

最后，将液体按杯子容量从大到小倒进杯子里，输出即可。

## Code
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,k;
long long s=0,sum,r,res[1005];
struct G
{
    int i;
    long long t,z;
}g[1005];
bool cmp(G a,G b)
{
    return a.z>b.z;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        g[i].i=i;
        cin>>g[i].t>>g[i].z;
        s+=g[i].t;
    }
    sort(g+1,g+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(sum+g[i].z>=s)
        {
            k=i;
            break;
        }
        sum+=g[i].z;
    }
    r=s;
    for(int i=1;i<=k;i++)
    {
        long long p=min(r,g[i].z);
        res[g[i].i]=p;
        r-=p;
    }
    cout<<n-k<<endl;
    for(int i=1;i<=n;i++)
        cout<<res[i]<<" ";
    return 0;
}
```
注意：杯子的容量和编号要使用结构体存储，因为最后要按输入顺序输出。

正在渲染内容...