Codeforce 999 D. Equalize the Remainders 解析(思維)

今天我們來看看CF999D
題目連結

題目
略，請直接看原題

前言

感覺要搞個類似$stack$的東西來儲存下一個沒滿的$\mod m$是哪一個才能避免$O(m^2)$的複雜度，沒想到反過來想，儲存前一個滿出來的是什麼就可以了。

想法

首先可能會想到，先把每個$mod$值都儲存到一個$vector<int> as[_n]$裡，然後從$mod=0$開始一直到$mod=m-1$，如果當前$mod$的數字太多，那就找最近的下一個$mod$還沒滿的值填補上去。然而這樣的複雜度要$O(m^2)$。
我一開始是想說看怎麼樣能利用類似$stack$的結構，去$O(1)$找到對於某個$mod=i$來說的下一個還沒滿的$mod$值，但是其實如果反過來想，每次如果有多出來的$mod$值，就先$push_back$到一個$vector$裡，那麼繼續遍歷$i=0\sim m-1$，當發現一個還沒滿的$mod$值時，$vector$末端的元素一定是靠當前$i$最近的。
然而會發現當前未滿的$mod=i$有可能需要後面的$mod>i$來填補，於是我們遍歷$i$時不要只到$m-1$，而是讓$i=0\sim 2m-1$，如此一來問題就解決了。

程式碼:

const int _n=2e5+10;  
ll t,tt,n,m,mm,k,ii,a[_n],cnt;  
VI as[_n],free;  
main(void) {ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);  
  cin>>n>>m;mm=m*2,k=n/m;rep(i,0,n){cin>>a[i];as[a[i]%m].pb(i);}  
  rep(i,0,mm){  
    ii=i%m;  
    if(SZ(as[ii])>k){  
      t=SZ(as[ii])-k;  
      rep(j,0,t)free.pb(as[ii][j]);  
    }  
    if(SZ(as[ii])<k){  
      t=min(SZ(free),k-SZ(as[ii]));  
      rep(j,SZ(free)-t,SZ(free)){  
        tt=a[free[j]]%m;if(tt>ii)tt-=m;  
        a[free[j]]+=ii-tt,cnt+=ii-tt;  
      }free.erase(free.end()-t,free.end());  
    }  
  }  
  cout<<cnt<<'\n';  
  rep(i,0,n)cout<<a[i]<<' '; cout<<'\n';  
  return 0;  
}  

$free$這個$vector$名稱已經存在了，需要$#define\ free\ [隨便一個字串]$
標頭、模板請點Submission看
Submission