题解 P5051 【[COCI2017-2018#7] Timovi】

Alex_Wei · 2019-01-17 21:58:23 · 题解

思路：把来回一趟看做一个整体

即 1,2,3……n,n-1……4,3,2（注意这里是 2）

共放了 2*(n-1) 次，共 2*(n-1)*k 人

计算出趟数 t，再模拟剩下来的人数

趟数=总人数/来回一趟的人数，即

剩余人数=总人数%来回一趟的人数，再模拟下去即可

时间复杂度：O(n)

具体思路见代码

#include<bits/stdc++.h>
using namespace std;
long long i[200020],n,m,k,t,no=1,pd=1;
int main()
{
    cin>>n>>k>>m; 
    t=m/(k*(n-1)*2);//趟数=总人数/来回一趟的人数
    for(int x=1;x<=n;x++)
        x==1||x==n?i[x]=t*k:i[x]=t*k*2;//每个队伍的人数=趟数（t）*每趟的人数（k*2），注意这里的1和n要特判一下
    m%=(k*(n-1)*2);//剩余的人数
    for(int x=1;m;x++){//还有人没有被分配在队伍里
        int p=n-abs(n-x),pe=min(m,k);//p:即将把人分配到第p个队伍里（这个计算公式可以手推），pe:可以分配的人数 
        i[p]+=pe,m-=pe;
    }
    for(int x=1;x<=n;x++)
        cout<<i[x]<<" ";
    return 0;
}

如果有错误请私信我，我会及时改正！