欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-04-15 08:56:54
题意: 设一个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,表示放入,这样就不需要考虑全局的问题了。
 
参考代码:
2018-10-06 Gym-101864F丨STL爽题丨想法
#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;
}
/*
*/
参考代码