题解：P11085 [ROI 2019] 学生座位 (Day 2)

LastKismet · 2025-07-01 18:24:21 · 题解

Sol

首先是一个经典贪心。

考虑只有一个班，如何分组最优？显然排序后两两依次分组，这样同组内两人高度差最小，必然最优。

考虑多个班，同一张桌子必然有 m 组人坐，怎么安排最优？同理，显然排序后各班同序号的组分成一起最优。

那么我们就可以对各序号依次选择最合适的桌子。问题变成：给出一些点，一些区间，选择一个最合适的区间使得题目中给出的代价最小。

这时候我们发现这个问题是有决策单调性的。由于更大的组中各班的小组都比上一大组中相应的组大，不难想到这一组最合适的区间左端点不小于上一组。倘若左端点小于上一组，那么上一组选这个左端点更小的区间就会更优。这个多想一想就会发现特别显然。

因此我们就可以决策单调性简单解决这个问题了。

Code

int n,m,k;
struct desk{ll l,r;}ds[N];
map<ll,ll> mp;
ll h[N];
vec<ll> v[N];
vec<ll> sum[N];
ll ans;

inline void solve(int l,int r,int pl,int pr){
    if(l>r)return;
    int md=l+r>>1,pm;ll tans=INF;
    rep(i,pl,pr){
        int a=lower_bound(v[md].begin(),v[md].end(),ds[i].l)-v[md].begin()-1;
        int b=upper_bound(v[md].begin(),v[md].end(),ds[i].r)-v[md].begin()-1;
        ll t=a*ds[i].l-sum[md][a]+sum[md][m<<1]-sum[md][b]-(m*2-b)*ds[i].r;
        if(t<tans){
            tans=t;
            pm=i;
        }
    }
    ans+=tans;
    solve(l,md-1,pl,pm);
    solve(md+1,r,pm,pr);
}

inline void Main(){
    read(m,n,k);
    rep(i,1,k)read(ds[i].l,ds[i].r),chmax(mp[ds[i].l],ds[i].r);
    int kk=0;
    for(auto i:mp)ds[++kk]={i.fir,i.sec};
    k=kk;
    rep(i,1,m){
        rep(j,1,n<<1)read(h[j]);
        sort(h+1,h+1+(n<<1));
        rep(j,1,n)v[j].pub(h[j*2-1]),v[j].pub(h[j*2]);
    }
    rep(i,1,n){
        v[i].pub(0);
        sort(v[i].begin(),v[i].end());
        sum[i].resize(m<<1|1);
        rep(j,1,m<<1)sum[i][j]=sum[i][j-1]+v[i][j];
    }
    solve(1,n,1,k);
    put(ans);
}