P5051 [COCI2017-2018#7] Timo

题目传送门

思路

由于题目给出的顺序是——

$1^{th}\to2\to3^{{th}\to\dots\to(n-1)}\to n^{th}$

$\to(n-1)^{th}\to(n-2)\to\dots\to2^{th}\to1\to2^{th}$

因为我们每走一回在开头和结尾只走了一次，而其他位数则走了两次，这样的话我们再分组的时候就可以不按照 $1 \to \dots\to n$ 来执行而可以分为 $1 \to \dots\to n-1$ 和 $n \to\dots\to 2$ 两段，这样我们就可以有效的缓解首尾出现次数的问题，并且可以方便分解，这样的话我们就可以将每次循环的时间复杂度变为乘法即将 $O(\dfrac{m}{k})$ 变为 $O(n)$ 就可以有效的解决 TLE 的问题,然后剩下的数就纯暴力将他们填上。

AC code

这个代码有点长——

#include<bits/stdc++.h>
using namespace std;
#define int long long //用宏定义将 int 变为 long long 防止精度问题 
int len,n,k,m,flag,a[1000005];
signed main(){
	cin>>n>>k>>m;
	len=m/((n-1)*k);//判断数据的组数 
	m-=len*(n-1)*k;//算出多余的人数 
	if(len%2==1){//分奇数和偶数进行判断 
		for(int i=1;i<=n;i++){
			if(i==1) a[i]+=k*(len/2+1);//因为是奇数次，所以开头要比结尾多上一次 
			else if(i==n) a[i]+=k*(len/2);
			else a[i]+=k*len;
		}
		for(int i=n;i>=1;i--){
			a[i]+=min(m,k);
			m-=min(m,k);
			if(!m) break;//如果没有人了，就退出 
		}
	}
	else if(len%2==0){
		for(int i=1;i<=n;i++){
			if(i==1 || i==n) a[i]+=k*(len/2);//偶数次就说明开头与结尾出现的次数相同 
			else a[i]+=k*len;
		}
		for(int i=1;i<=n;i++){
			a[i]+=min(m,k);
			m-=min(m,k);
			if(!m) break;
		}
	}
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	return 0;
}