http://www.zybbs.org/JudgeOnline/problem.php?id=1106
http://main.edu.pl/en/archive/oi/14/tet
題目大意：誒呀我不說了就是個消方塊的游戲和祖瑪似的……
腫么搞這個題呢？首先如果對于兩個相同數(shù)字的方塊，如果他們之間還有可以配對的兩個方塊，顯然先消掉中間的方塊更優(yōu)。但是如果他們之間有k個無法配對的方塊，我們就至少需要k次交換消掉現(xiàn)在的這兩塊。我們就可以統(tǒng)計一下每兩個相同的方塊之間有多少無法配對的方塊。可以用一個樹狀數(shù)組來維護……
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#define lowbit(x) x&-x;
#define mn 50000
using namespace std;
int n,ans,x,pos[mn],v[mn<<1];
void Modify(int x,int val){
while(x<=n<<1) v[x]+=val,x+=lowbit(x);
}
int Get(int x){
int sum=0;
while(x>0) sum+=v[x],x-=lowbit(x);
return sum;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n<<1;i++){
scanf("%d",&x);
if(!pos[x]){
pos[x]=i;
Modify(i,1);
}else{
ans+=Get(i)-Get(pos[x]-1)-1;
Modify(pos[x],-1);
}
}
printf("%d\n",ans);
return 0;
}
更多文章、技術交流、商務合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
