題目鏈接：點擊查看

題目大意：給出一個1~n的排列，現在要求選擇一個合適的分割點，將整個排列分為兩個部分，要求通過適當的移動使得前半部分的所有數值都小于后半部分的數值，現在給出移動每個數字所花費的代價，輸出最小代價

題目分析：斷斷續續想了三天的一個題，終于算是有點小突破了。。可以試著寫寫題解鞏固一下了

說在前面，這個題目可以視為二維偏序問題，第一維下面稱作分割點，第二維下面稱作斷點，注意區分

分割點：可以將原排列分為前半部分和后半部分兩個部分

斷點：表示在經過移動后，前半部分的最大值與后半部分的最小值之間的那個點

其實讀完題后，能夠秒出一個暴力的思路，n個數，會出現n+1個分割點，我們可以枚舉這n+1個分割點，將整個排列分為不同的兩個部分，分割點確定后，移動的方式還有n+1種，因為我們還需要確定作為分隔最終序列的斷點 k ，也就是說：

如果某個數在后半部分，且這個數值小于斷點 k

如果某個數在前半部分，且這個數值大于斷點 k

滿足以上兩種情況的數都是會積累貢獻的，不過光是枚舉分割點和斷點就已經到了n*n的時間復雜度了，但是顯然n*n的時間復雜度在這個題目中是不合適的，我們需要選擇適當的數據結構來進行優化

其實換個角度想，這就轉換成了一個二維偏序問題，我們枚舉的分割點是第一維的序列，而枚舉的斷點是第二維的序列，一般處理二維偏序問題通常是需要借助線段樹的，我們可以利用線段樹維護第二維斷點的信息，每個區間節點代表的是以當前點為斷點所能提供的貢獻，顯然我們需要的答案是n+1個斷點中的最小值，至于每個節點的貢獻我們該如何儲存呢，因為上面提到了，若某個數值有貢獻，必須滿足上面分類的兩個條件，我們可以O(n)枚舉第一維的分割點，同時用線段樹O(logn)維護第二維的斷點，一開始初始化我們可以假設所有的點都在后半部分，隨后從[1,n-1]枚舉第一維分割點，同時實時維護最小值就可以了，因為題目要求初始時分割的兩個部分非空，所以第一維分割點枚舉的區間是[1,n-1]而不是[0,n]

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;const LL inf=0x3f3f3f3f3f3f3f3f;const int N=2e5+100;int p[N],a[N];struct Node {int l,r;LL mmin,lazy; }tree[N<<2];void pushup(int k) {tree[k].mmin=min(tree[k<<1].mmin,tree[k<<1|1].mmin); }void pushdown(int k) {if(tree[k].lazy){LL lz=tree[k].lazy;tree[k].lazy=0;tree[k<<1].mmin+=lz;tree[k<<1].lazy+=lz;tree[k<<1|1].mmin+=lz;tree[k<<1|1].lazy+=lz;} }void build(int k,int l,int r) {tree[k].l=l;tree[k].r=r;tree[k].mmin=tree[k].lazy;if(l==r)return;int mid=l+r>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r); }void update(int k,int l,int r,LL val) {if(tree[k].r<l||tree[k].l>r)return;if(tree[k].l>=l&&tree[k].r<=r){tree[k].mmin+=val;tree[k].lazy+=val;return;}pushdown(k);update(k<<1,l,r,val);update(k<<1|1,l,r,val);pushup(k); }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",p+i);for(int i=1;i<=n;i++)scanf("%d",a+i);build(1,0,n);for(int i=1;i<=n;i++)//初始化：因為此時所有點都在后半部分，所以可以做出貢獻的值是需要小于斷點的update(1,p[i],n,a[i]);//換句話說，會對大于當前值的斷點做出貢獻LL ans=inf;for(int i=1;i<n;i++){update(1,p[i],n,-a[i]);//每次分割點向右移動，會讓p[i]點從后半部分來到前半部分update(1,0,p[i]-1,a[i]);//這樣對分割點的貢獻也就變成了，會對小于當前值的斷點做出貢獻ans=min(ans,tree[1].mmin);//實時維護最小值}printf("%lld\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1295E Permutation Separation(线段树+二维偏序，好题)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。