题意

\(n\) 个人，两两决斗，赢得 \(1\) 分，输得 \(0\) 分。

但是统计比分有误，请推算出一组正确的比分，使推算出来的比分和原比分差距之和最小。

分析

按比分序列 \(a\) 从小到大排序。

第 \(i\) 个人的比分至少是 \(i\times(i-1)/2\) 。

若 $ a_i < i\times(i-1)/2$ ，则将 \(a_i\) 改为 \(i \times (i-1) / 2\)。

若 \(a\) 序列的总和 \(sum > n\times(n-1)/2\) ，则减去多余的部分。

code

#include <bits/stdc++.h>
using namespace std;

const int N = 55;

int a[N];

int main()
{
	int T;
	scanf("%d",&T);

	while (T--)
	{
		int n;
		long long ans=0;
		long long sum=0;

		scanf("%d",&n);
		for (int i=0; i<n; i++) scanf("%d",&a[i]);

		sort(a,a+n);

		sum=a[0];
		for (int i=2; i<=n; i++) //前i个人
		{
			sum+=a[i-1];//前i个人的和
			if(sum>=i*(i-1)/2) continue;//如果大于直接继续，最后在统一减
			else //如果小于则需要添加场次
			{
				ans+=abs(sum-(i*(i-1)/2));
				sum=i*(i-1)/2;
			}
		}

		if(sum>=n*(n-1)/2) ans+=sum-(n*(n-1)/2);//统一减
		else ans+=(n*(n-1)/2)-sum;//如果小于则添加场次

		printf("%lld\n",ans);
	}

	return 0;
}

【题解】 SP10231 AMR11D - Wizarding Duel