首页 > > 程序设计 > C/C++ >

2018-10-06 Gym-101864F丨STL爽题丨想法

2018-10-08 01:30:38来源：博客园阅读 ()

题意：

　　设一个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;
}
/*
*/
参考代码
 