CF1758D 题解

前言

题目传送门！

更好的阅读体验？

用一种非常麻烦的做法把自己写自闭了，和题解区不一样，但是方法困难很多。

思路

代码

属于混乱邪恶了，凑合着看看。

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n, ans[300005];
long long calc()
{
	long long sum = 0;
	for (int i = 1; i <= n; i++) sum += ans[i];
	return sum - 1ll * (ans[1] - ans[n]) * (ans[1] - ans[n]);
}
void solve()
{
	scanf("%d", &n);
	if (n == 3) {puts("3 6 7"); return;}
	int x = ceil((1.0 * (-2 * n) / (n + 1) + n) / 2.0);
	ans[1] = x; for (int i = 2; i <= n; i++) ans[i] = x + i;
	long long sum = calc();
	if (n & 1)
	{
		for (int i = 1; i <= n; i++) ans[i] <<= 1;
		sum = -calc();
		for (int i = 1; i <= n; i++) ans[i] += (sum / n);
		sum %= n;
		
		for (int i = n - 1; sum && i >= 2; i--)
			while (sum && ans[i] + 1 < ans[i + 1])
				sum--, ans[i]++;
	}
	else
	{
		for (int i = 2; sum && i < n; i++)
			while (ans[i] > ans[i - 1] + 1)
				sum--, ans[i]--;
	}
	for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
	puts("");
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--) solve();
	return 0;
}

希望能帮助到大家！