题解 CF195B 【After Training】

· · 题解

话不多说先上翻译:

在一支球队完成了对欧洲足球锦标赛的培训之后，瓦莱里克被委托收集球并将其分类到篮子中。总的来说，体育场有n个球和m个篮筐。篮子从左到右排成一排，并从1到m进行编号。球从1到n编号。

瓦莱里克决定按照以下方案，按球数递增的顺序对球进行分类。他会将每个新球放入最少的球数放入篮子。如果他有几个变种，他会选择更靠近中间的篮子。这意味着他选择了 最小的篮子，其中i是篮子的数量。如果在这种情况下，瓦莱里克（Valeric）仍然有多个变体，他选择数量最少的篮筐。

根据Valeric的方案，为每个球印上将要运到的篮筐编号。

请注意，这些球以递增的顺序分类到篮子中，也就是说，第一个球先移动，然后第二个球移动，依此类推。 emmm,谷歌机器翻译的,感性的理解一下吧

首先分析一下,我们会发现这个题目还是简单的,重难点就是如何算出每一个球放进箱子

这时就有一个奇怪的贪心思路:就是每次有多个选择时放进箱子,那么下一次的最优解一定是与之对称的,这个在接下来的代码中有很好的的体现,不明白的可以结合代码

#include<bits/stdc++.h>
#define N 1000000000
typedef long long ll;
using namespace std;
int main(){
    ll n,m;
    cin >> n >> m;
    ll i = (m + 1)/2;
    ll vals[m];
    ll j = 0;
    bool flag;
    if(m%2 == 1){//先预处理奇偶的影响
        flag = true;
    } 
    else {
        flag = false;
    }
    while(1){
        if(j < 0 || j > m){//不满足边界条件
            break;
        }
        vals[j] = i;//记录答案
        j++;
        if(flag){//这就是那个思路了(划重点)
            i = i - j;
        } 
        else {
            i = i + j;
        }
        flag = !flag;
    }
    cout << endl;
    for(ll p = 0; p < n ; p++){//输出
        cout << vals[p%m] << endl;
    }
    return 0;
}