題意：有 $m$ 個(gè)班，每個(gè)班有 $2n$ 個(gè)人，他們的身高給定。有 $k$ 種雙人桌，每張桌子有兩個(gè)屬性值 $L_i,R_i$,一個(gè)身高為 $h$ 的人坐第 $i$ 種桌子的不舒適度為 $h$ 到區(qū)間 $[L_i,R_i]$ 的最小距離。你需要買 $n$ 張桌子，對每個(gè)班安排每個(gè)人坐哪張，使得總不舒適度最小。注意所有班用同一套桌子。

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

考場buff看出了所有神仙貪心結(jié)論，現(xiàn)在不會(huì)證了……有空再補(bǔ)吧。

首先把每個(gè)班的人按照高度排序，這樣一定是相鄰的兩個(gè)人兩兩坐一個(gè)桌子。

因?yàn)槊拷M的高度構(gòu)成的區(qū)間是不會(huì)相交的，然后可以證明所有班的同一編號的組一定坐同一組桌子。

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

然后又可以證明所有班的第 $i$ 組對應(yīng)的桌子編號是單調(diào)的。

但是每一組在每張桌子上的代價(jià)不是單峰的，因?yàn)樽雷幼蠖它c(diǎn)加一點(diǎn)，右端點(diǎn)加很多，就離二元組較高的那個(gè)近了。所以走指針是不行的。

考慮分治。對當(dāng)前組的區(qū)間中點(diǎn)求出最優(yōu)決策，然后兩邊限制決策范圍遞歸。這樣雖然決策分的不均勻，但組是均勻的，只會(huì)遞歸 $O(\log n)$ 層，每層會(huì)算 $O(m)$ 次，復(fù)雜度 $O(m\log n)$。

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <algorithm> #include <utility> #include <vector> #define MAXN 1000005 using 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; }

總結(jié)

以上是生活随笔為你收集整理的【ROI 2019 Day2】课桌【贪心】【决策单调性】【分治】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。