題目鏈接：點擊查看

題目大意：七夕節因牛郎織女的傳說而被扣上了「情人節」的帽子。于是TYVJ今年舉辦了一次線下七夕祭。Vani同學今年成功邀請到了cl同學陪他來共度七夕，于是他們決定去TYVJ七夕祭游玩。

TYVJ七夕祭和11區的夏祭的形式很像。矩形的祭典會場由N排M列共計N×M個攤點組成。雖然攤點種類繁多，不過cl只對其中的一部分攤點感興趣，比如章魚燒、蘋果糖、棉花糖、射的屋……什么的。Vani預先聯系了七夕祭的負責人zhq，希望能夠通過恰當地布置會場，使得各行中cl感興趣的攤點數一樣多，并且各列中cl感興趣的攤點數也一樣多。

不過zhq告訴Vani，攤點已經隨意布置完畢了，如果想滿足cl的要求，唯一的調整方式就是交換兩個相鄰的攤點。兩個攤點相鄰，當且僅當他們處在同一行或者同一列的相鄰位置上。由于zhq率領的TYVJ開發小組成功地扭曲了空間，每一行或每一列的第一個位置和最后一個位置也算作相鄰。現在Vani想知道他的兩個要求最多能滿足多少個。在此前提下，至少需要交換多少次攤點。

題目分析：中文題目，題意不難理解，首先我們應該知道，行和列是兩個獨立的個體，在交換相鄰兩行的時候，對列是沒有貢獻的，同理，在交換相鄰兩列的時候，對行也是沒有貢獻的，所以我們只針對于交換相鄰兩列的情況討論：

首先列數一共有m列，攤數一共有t個，若t%m不為0，那么對于列是無解的，如果有解的話，那么每一列最后都需要有t/m個攤點才行，而相鄰兩個可以交換，我們先假設當前的模型不是環狀的而是線狀的，a[1]是開頭，a[m]是結尾，這樣一來就能線性遞推出答案了，比如：

若a[i]>t/m，則a[i]需要給a[i+1] a[i]-t/m個攤點

若a[i]<t/m，則a[i+1]需要給a[i] t/m-a[i]個攤點

用上面的關系就能線性遞推出答案了

但實際上題目并不是這么簡單的，題目將線性的模型改成了環狀的模型，也就是說必定存在著一種最優解，能讓答案最小，換句話說，必定有兩個相鄰的列之間沒有發生攤位的交換，就像上面提到的線性模型一樣，開頭節點和末尾節點之間就沒有發生攤位的交換，在這種情況下求最優解，我們最樸素的方法是枚舉每一個斷點，一共需要枚舉n次，每次都需要進行O(n)的遞推，才能計算出答案，從而維護出最小值，總的時間復雜度為n*n+m*m，這個題目給出的n和m都達到了1e5的級別，所以n*n肯定會超時的，我們需要想辦法優化

我們可以一開始就讓a[i]數組的每一項都減去t/m，最后結果為正說明需要往后面扔，為負說明需要從后面拿，這樣我們維護一個前綴和sum[i]，第i項對答案的貢獻就是abs(sum[i])了，其實思想和上面的方法類似，只不過上面的思想相當于模擬整個過程，而這里的思想是將模型抽象出來，轉換為數學公式而已了，比如第i個位置的貢獻是a[i]，先不管他的正負，我們都需要將a[i]先轉移(拿走或提供)給a[i+1]，然后再計算a[i+1]的貢獻，隨后再將a[i+1]的貢獻轉移給a[i+2]，如此往復就是一個前綴和了，并且當前前綴和的最后一項一定等于0，即sum[m]=0

但上述轉換只是換了種方法求每個位置對答案的貢獻，實質上時間復雜度還是O(n)，并沒有起到優化的作用，所以我們需要繼續轉換，到這里我們發現對于求答案，也只能優化為O(n)了，實在是沒有辦法再優化了，那么我們就只能著手于優化另一個O(n)，也就是枚舉n個端點選出最小值的過程了

因為有了前綴和sum[i]的輔助，我們可以設置某個斷點k，此時第k+1個點充當第一個點，第k個點充當最后一個點，這樣我們將剛才求得的前綴和稍加轉換：

第幾項? ?前綴和

a[k+1]? ? sum[k+1]-sum[k]

a[k+2]? ? sum[k+2]-sum[k]

....

a[m]? ? ? ?sum[m]-sum[k]

a[1]? ? ? ? sum[1]+sum[m]-sum[k]

....

a[k]? ? ? ? sum[k]+sum[m]-sum[k]

這樣我們在知道斷點的下標后，就可以O(1)求出所需要的前綴和了，也就不需要每次再用O(m)重新維護前綴和了

因為我們在上面提到過，sum[m]=0，那么上面的每一項都可以總結為一個通項了，對于第i項，他的前綴和就是sum[i]-sum[k]，那么當前位置對答案的貢獻也就是abs(sum[i]-sum[k])，我們現在只要找到k，使得i=[1,m]的貢獻和最小就可以了，上面我們最樸素的方法是暴力枚舉，線性維護最小值，但被我們直接駁回了，我們通過觀察以及總結可以得出結論，若想讓上面的式子貢獻和最小，讓sum[k]選取sum數組的中位數即可，這樣我們只需要對sum數組排序，時間復雜度為nlogn，忽略其余常數的話，這個題目的額時間復雜度就優化為nlogn+mlogm了，完美解決

不得不提一句，這個題目和“貨倉選址”那個題目又有點不同，貨倉選址那個題目也是讓在數軸上選取一個位置，使得abs(a[i]-x)的貢獻和最小，可以得出的結論是：

當n為奇數時，貨倉建在a[n/2+1]處最優

若n為偶數時，貨倉建在a[n/2]~a[n/2+1]之間(閉區間)的任何位置都是最優解

所以在做這個題目的時候，我直接按照分類討論，當n為奇數時，求得的中位數是(a[n/2]~a[n/2+1])/2，但只得了90分，最后一拍腦瓜才知道，貨倉選址這個題目的中位數是可以在數軸上任意選取的，但這個題目的中位數是只能再sum數組中選取，所以如果除以2的話，求出來的答案可能不是sum數組中的元素，所以求出來的答案就不滿足題意了

那么對于這個題目，我們也無需分奇偶討論了，統統以sum[(n+1)/2]作為中位數就可以了

還有一個細節需要注意，就是前綴和和最終答案可能會爆int，記得開longlong就好了

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int n,m,t;LL ans_r,ans_c;struct Pos {int x,y; }a[N];LL c[N];bool solve_r()//處理行 {if(t%n)return false;memset(c,0,sizeof(c));for(int i=1;i<=t;i++)//記錄每一列有多少個攤位c[a[i].x]++;for(int i=1;i<=n;i++)//維護前綴和c[i]=c[i]-t/n+c[i-1];sort(c+1,c+1+n);//排序LL temp=c[(n+1)/2];//中位數ans_r=0;for(int i=1;i<=n;i++)//計算貢獻和ans_r+=llabs(c[i]-temp);return true; }bool solve_c()//處理列，同上 {if(t%m)return false;memset(c,0,sizeof(c));for(int i=1;i<=t;i++)c[a[i].y]++;for(int i=1;i<=m;i++)c[i]=c[i]-t/m+c[i-1];sort(c+1,c+1+m);LL temp=c[(m+1)/2];ans_c=0;for(int i=1;i<=m;i++)ans_c+=llabs(c[i]-temp);return true; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);scanf("%d%d%d",&n,&m,&t);for(int i=1;i<=t;i++)scanf("%d%d",&a[i].x,&a[i].y);bool flag_c=solve_c();bool flag_r=solve_r();if(flag_c&&flag_r)printf("both %lld\n",ans_c+ans_r);else if(flag_c)printf("column %lld\n",ans_c);else if(flag_r)printf("row %lld\n",ans_r);elseprintf("impossible\n");return 0; }

?

總結

以上是生活随笔為你收集整理的CH - 0502 七夕祭(思维+中位数优化+前缀和优化)的全部內容，希望文章能夠幫你解決所遇到的問題。

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