题解：CF1607H Banquet Preparations 2

MonKeySort_ZYczc · 2026-11-12 12:20:50 · 题解

诶这个是不是很显然（）
以下令 a_i',b_i' 分别是吃后的 a_i,b_i。

思路流程

那你两个对要一样至少 a_i+b_i-m_i 要相同吧。所以可以先桶排，用 vector 维护 a_i+b_i-m_i=t 的 i，那就转化为 a_i+b_i-m_i 相同的子问题。
那这个咋做。你发现 a_i+b_i-m_i 相同的情况下一个数 a_i' 确定后 b_i' 自然确定，于是不用管 b_i，判断 a_i' 相同就行。
现在你发现 a_i' 取值其实是一个区间，具体的，是 [\max(0,a_i-m_i),a_i-\max(m_i-b_ia,0)]。非常 Amazing 啊，所以你会发现每一个 a_i 可以最后变成 x 当且仅当 a_i=x。
重新表述一下。给你若干条线段，每条线段上至少要选一个点（表示这个对 a_i' 变成几），求最少点数。经典的点覆盖线段的问题，贪心一下就行，而方案顺便记录一下就行了。
复杂度 O(Tn\log n)，注意精细一点实现，不要写成 O(TV) 有关的了。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define debug(i) cout<<"Cute_MKS "<<i<<' '
#define pii pair<int,int>
#define mkp(a,b) make_pair(a,b)
#define ll long long
#define fi first
#define sc second
const int N=1e6+10;
int T,n,a[N],b[N],m[N],sum,ans[N];
vector<int>v[N]; 
inline void clr(){sum=0;for(int i=1;i<=n;i++) v[a[i]+b[i]-m[i]].clear();}
inline void sol()
{
    cin>>n;
    set<int>s;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i]>>m[i],v[a[i]+b[i]-m[i]].push_back(i),s.insert(a[i]+b[i]-m[i]);
    vector< pii >t;
    for(auto it=s.begin();it!=s.end();it++)
    {
        int i=*it;
        t.clear();
        for(int j=0;j<v[i].size();j++) t.push_back(mkp(a[v[i][j]]-max(m[v[i][j]]-b[v[i][j]],0),v[i][j]));
        sort(t.begin(),t.end());
        int p=-1;
        for(int j=0;j<t.size();j++) 
        {
            if(max(a[t[j].sc]-m[t[j].sc],0)>p) sum++,p=t[j].fi;
            ans[t[j].sc]=a[t[j].sc]-p;
        }
    }
    cout<<sum<<'\n';
    for(int i=1;i<=n;i++) cout<<ans[i]<<' '<<m[i]-ans[i]<<'\n';
    clr();
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) sol();
}