洛谷P5051 [COCI2017-2018#7] Timovi

//翻译不过来，直接展示中文版：

题目描述

把m个人放在n个队伍里。 规则：

• 每次放k个人
• 顺序为1th->2th->3th->.......->(n−1)th->nth->(n−1)tℎ->(n−2)tℎ->……->2th->1th->2th->……
• 一直重复到当前剩余人数<k为止。此时剩下的人全部放在当前队里

输入格式： 一行，分别是n、k、mn、k、m

输出格式： 一行，n个数，分别是每个队伍分到的人数

输入输出样例

输入 #1

2 1 3

输出 #1

2 1

输入 #2

3 2 7

输出 #2

2 3 2

输入 #3

4 5 6

输出 #3

5 1 0 0

说明/提示

In test cases worth a total of 40 points, it will hold M / K ≤ 200 000.

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

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

共放了 2∗(n−1) 次，共 2∗(n−1)∗k 人

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

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

t=m/(2∗(n−1)∗k)

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

时间复杂度：O(n)

废话不多说，直接上code：

#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;
}

记得点赞哟！