CF195B After Training 题解

· · 题解

题目传送门

思路

本题很水……

根据题意，我们可以看出输出顺序是：从中间开始，先输出左边，再输出右边。

我们可以模拟第一个样例：

我们先找出中间的桶，也就是第二个桶。

对于第二个球，我们要找往左边的一个桶，也就是第一个桶。我们之所以要找这个桶，是因为题目说了，对于距离中间一样的桶，要找最靠左边的一个桶。

对于第三个球，我们要找第三个桶。

对于第四个球，我们要再装到第二个桶里，因为三个桶装的球数量一样。

但是，偶数是另一个情况：

我们找到中间后，要先从右边开始，因为有两个桶离中间的距离一样。当有四个桶时，我们的输出便变成了：

2
3
1
4

为什么是这样呢？因为共有 4 个桶，一半是 2.5，依题意，中间的桶（即编号距离 2.5 桶最近的桶）分别为二号和三号桶。二号桶要排在三号桶之前，三号要在一号之前，而四号要在最后，因此，顺序才会是这样的。

实现方法

我们要分两类讨论，即当 m 是奇数的时候和当 m 是偶数的时候。

实现方法其实不难，两种的实现方法基本上一样。可以定义一个 now 变量，表示这一次选择的桶与上一次选择的桶的差距。

当 m 是奇数时，如果 now 是奇数，那这一次选择的桶的编号会比上一次选择的大，否则，如果 now 是偶数，则是变小。

当 m 是偶数时，与奇数相反。

为什么呢？

前面讲过，当 m 为偶数时，第一次选择的时候回有两个桶距离中间的距离会是一样的，所以第一次要加，而不是减。

当现在要选择的桶编号小于 0 或者大于 m 的时候，便重新开始，从中间开始往外遍历。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    int curr=m/2; //从中间开始
    if(m%2) curr+=1;
    int now=0;
    for(int i=1;i<=n;i++){
        now++;
        printf("%d\n",curr); 
        if(m%2==1) { //分两类讨论
            if(now%2==0) curr+=now;
            else curr-=now;
        }
        else {
            if(now%2==0) curr-=now;
            else curr+=now;
        }
        if(curr<1||curr>m){ //重新开始
            curr=m/2;
            if(m%2) curr+=1;
            now=0;
        }
    }
    cout<<endl;
    return 0;
}

请勿抄题解！