【ROI 2019 Day2】课桌【贪心】【决策单调性】【分治】,步步高i308

文件名：【ROI 2019 Day2】课桌【贪心】【决策单调性】【分治】,步步高i308 【ROI 2019 Day2】课桌【贪心】【决策单调性】【分治】

题意：有 $m$ 个班，每个班有 $2n$ 个人，他们的身高给定。有 $k$ 种双人桌，每张桌子有两个属性值 $L_i,R_i$,一个身高为 $h$ 的人坐第 $i$ 种桌子的不舒适度为 $h$ 到区间 $[L_i,R_i]$ 的最小距离。你需要买 $n$ 张桌子，对每个班安排每个人坐哪张，使得总不舒适度最小。注意所有班用同一套桌子。

$n\cdot m,k\le 2\times 10^5,L_i,R_i,h\le 10^9$

考场buff看出了所有神仙贪心结论，现在不会证了……有空再补吧。

首先把每个班的人按照高度排序，这样一定是相邻的两个人两两坐一个桌子。

因为每组的高度构成的区间是不会相交的，然后可以证明所有班的同一编号的组一定坐同一组桌子。

然后把被完全包含的桌子去掉后按 $L$ 排序，这样 $R$ 也是有序的。

然后又可以证明所有班的第 $i$ 组对应的桌子编号是单调的。

但是每一组在每张桌子上的代价不是单峰的，因为桌子左端点加一点，右端点加很多，就离二元组较高的那个近了。所以走指针是不行的。

考虑分治。对当前组的区间中点求出最优决策，然后两边限制决策范围递归。这样虽然决策分的不均匀，但组是均匀的，只会递归 $O(\log n)$ 层，每层会算 $O(m)$ 次，复杂度 $O(m\log n)$。

#include <iostream>#include <cstdio>#include <cstring>#include <cctype>#include <algorithm>#include <utility>#include <vector>#define MAXN 1000005using namespace std;inline int read(){int ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans;}typedef pair<int,int> pi;inline bool cmp(const pi& a,const pi& b){return a.first==b.first? a.second>b.second:a.first<b.first;}pi t[MAXN],p[MAXN];vector<int> lis[MAXN];typedef long long ll;int val[MAXN],cnt,n,m,k;ll s[MAXN],sum;ll calc(pi p){ll ans=0;int pos=lower_bound(val+1,val+cnt+1,p.first)-val-1;ans+=(ll)p.first*pos-s[pos];pos=upper_bound(val+1,val+cnt+1,p.second)-val-1;ans+=s[cnt]-s[pos]-(ll)(cnt-pos)*p.second;return ans;}void solve(int l,int r,int pl,int pr){if (l>r) return;int mid=(l+r)>>1;cnt=0;for (int i=1;i<=m;i++) val[++cnt]=lis[i][mid<<1],val[++cnt]=lis[i][mid<<1|1];sort(val+1,val+cnt+1);for (int i=1;i<=cnt;i++) s[i]=s[i-1]+val[i];int k=pl;ll ans=calc(p[k]),t;for (int i=pl+1;i<=pr;i++)if ((t=calc(p[i]))<ans)ans=t,k=i;sum+=ans;solve(l,mid-1,pl,k),solve(mid+1,r,k,pr);}int main(){m=read(),n=read(),k=read();for (int i=1;i<=k;i++) t[i].first=read(),t[i].second=read();sort(t+1,t+k+1,cmp);for (int i=1;i<=k;i++){if (cnt&&t[i].second<=p[cnt].second) continue;p[++cnt]=t[i];}k=cnt;for (int i=1;i<=m;i++){lis[i].resize(n<<1);for (int j=0;j<(n<<1);j++) lis[i][j]=read();sort(lis[i].begin(),lis[i].end());}solve(0,n-1,1,k);cout<<sum;return 0;}