自助建站在线快速建站,广告联盟有哪些平台,wordpress采集文章内容,儒枫网网站建设题意#xff1a;有 mmm 个班#xff0c;每个班有 2n2n2n 个人#xff0c;他们的身高给定。有 kkk 种双人桌#xff0c;每张桌子有两个属性值 Li,RiL_i,R_iLi,Ri,一个身高为 hhh 的人坐第 iii 种桌子的不舒适度为 hhh 到区间 [Li,Ri][L_i,R_i][Li,Ri] 的最小距离。你…题意有 mmm 个班每个班有 2n2n2n 个人他们的身高给定。有 kkk 种双人桌每张桌子有两个属性值 Li,RiL_i,R_iLi,Ri,一个身高为 hhh 的人坐第 iii 种桌子的不舒适度为 hhh 到区间 [Li,Ri][L_i,R_i][Li,Ri] 的最小距离。你需要买 nnn 张桌子对每个班安排每个人坐哪张使得总不舒适度最小。注意所有班用同一套桌子。
n⋅m,k≤2×105,Li,Ri,h≤109n\cdot m,k\leq 2\times 10^5,L_i,R_i,h\leq 10^9n⋅m,k≤2×105,Li,Ri,h≤109
考场buff看出了所有神仙贪心结论现在不会证了……有空再补吧。
首先把每个班的人按照高度排序这样一定是相邻的两个人两两坐一个桌子。
因为每组的高度构成的区间是不会相交的然后可以证明所有班的同一编号的组一定坐同一组桌子。
然后把被完全包含的桌子去掉后按 LLL 排序这样 RRR 也是有序的。
然后又可以证明所有班的第 iii 组对应的桌子编号是单调的。
但是每一组在每张桌子上的代价不是单峰的因为桌子左端点加一点右端点加很多就离二元组较高的那个近了。所以走指针是不行的。
考虑分治。对当前组的区间中点求出最优决策然后两边限制决策范围递归。这样虽然决策分的不均匀但组是均匀的只会递归 O(logn)O(\log n)O(logn) 层每层会算 O(m)O(m)O(m) 次复杂度 O(mlogn)O(m\log n)O(mlogn)。
#include iostream
#include cstdio
#include cstring
#include cctype
#include algorithm
#include utility
#include vector
#define MAXN 1000005
using namespace std;
inline int read()
{int ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
typedef pairint,int pi;
inline bool cmp(const pi a,const pi b){return a.firstb.first? a.secondb.second:a.firstb.first;}
pi t[MAXN],p[MAXN];
vectorint lis[MAXN];
typedef long long ll;
int val[MAXN],cnt,n,m,k;
ll s[MAXN],sum;
ll calc(pi p)
{ll ans0;int poslower_bound(val1,valcnt1,p.first)-val-1;ans(ll)p.first*pos-s[pos];posupper_bound(val1,valcnt1,p.second)-val-1;anss[cnt]-s[pos]-(ll)(cnt-pos)*p.second;return ans;
}
void solve(int l,int r,int pl,int pr)
{if (lr) return;int mid(lr)1;cnt0;for (int i1;im;i) val[cnt]lis[i][mid1],val[cnt]lis[i][mid1|1];sort(val1,valcnt1);for (int i1;icnt;i) s[i]s[i-1]val[i];int kpl;ll anscalc(p[k]),t;for (int ipl1;ipr;i)if ((tcalc(p[i]))ans)anst,ki;sumans;solve(l,mid-1,pl,k),solve(mid1,r,k,pr);
}
int main()
{mread(),nread(),kread();for (int i1;ik;i) t[i].firstread(),t[i].secondread();sort(t1,tk1,cmp);for (int i1;ik;i){if (cntt[i].secondp[cnt].second) continue;p[cnt]t[i];}kcnt;for (int i1;im;i){lis[i].resize(n1);for (int j0;j(n1);j) lis[i][j]read();sort(lis[i].begin(),lis[i].end());}solve(0,n-1,1,k);coutsum;return 0;
}
