題意： 設一個1-n的空間，初始1-k位置占了人，每次操作將x位置的人移動到y位置，保證輸入操作合法，求，每次操作後，空間無人的間隔，有多少個（比如01000100100有4個）。 思路： 題目給的N很大，無法用數組去模擬，一開始很蒙，但是感謝隊友的想法，我寫了很短的代碼解了這道題。首先，要觀察到， ...
題意： 設一個1-n的空間，初始1-k位置占了人，每次操作將x位置的人移動到y位置，保證輸入操作合法，求，每次操作後，空間無人的間隔，有多少個（比如01000100100有4個）。 思路： 題目給的N很大，無法用數組去模擬，一開始很蒙，但是感謝隊友的想法，我寫了很短的代碼解了這道題。首先，要觀察到，每次移動人，對答案的影響，其實只和這個位置相鄰的兩個位置有關，比如，x位置左右為空的話，取走x上的人，會使得兩個間隔合併，於是ans-1。以此類推對於y，如果兩個位置為空的，y位置放上人，會使得ans+1。 同理舉一反三，可以想到三種情況：1x1,0x1(1x0),0x0,（y同理，且對答案的影響與x相反）那麼還有一個困難，前k個位置一開始是有人的。我們可以這樣考慮，因為答案只受到每次x和y以及相鄰的幾個位置有關，那麼，對於這幾個位置，我們只需要判斷是否小於k，你肯定會問，之後呢？ 為了方便，用map模擬，對於為0的位置判斷是否小於k，就可以知道是否為空，之後，我們對x位置賦2表示被移走，對y位置賦1，表示放入，這樣就不需要考慮全局的問題了。 參考代碼：
#include<stdio.h> #include<unordered_map> std::unordered_map<int,int> mp; int T,Ti,n,k,q; int change(int x) { int l=1,r=1;//has one there; if(mp[x-1]==2||(x-1>k&&mp[x-1]==0))l=0; if(mp[x+1]==2||(x+1>k&&mp[x+1]==0))r=0; return r+l-1;//both are ones,return 1; } int main(){ scanf("%d",&T); while(Ti++<T){ scanf("%d%d%d",&n,&k,&q); printf("Case %d:\n",Ti); mp[0]=mp[n+1]=1; int ans=1; for(int i=1,x,y;i<=q;i++){ scanf("%d%d",&x,&y); ans+=change(x); mp[x]=2;//one on 'x' has been taken; ans-=change(y); mp[y]=1; printf("%d\n",ans); } mp.clear(); } return 0; } /* */參考代碼
