Codeforces Round #728 (Div. 1) problemA 题解_codeforces round 728 (div. 1)

Codeforces Round #728 (Div. 1) problemA

题目大意是john有个农场，给出从起始点到终点的最短路径，且不存在时间循环（此处为重点），求构造农场的最小开销。给出的d全为正值。

不存在时间循环，其意为不存在负环，那么我们就可以构造一个循环为0的环，比如0->1,d1=1，构造一个1->0,d’1=-1，构造出0环。对整个图构造出两两的为0的循环，然后在此图的基础上删去一些边来达到最短路，且满足原给出路径的图。

这里假设有4个点分别为1~4
若是构造出两两相连的点，在这里省去正向和负向边，留下其他边做出简化

不妨先从3个点开始，则有

构造出如上的三点图，则是1->2->3,可以顺着构造一张图，然后其他构造两两相连的反图，距离为两点间的最短距离，如红色线所示。

在这里解释为什么要构造2->3而不是1->3的线， 题目给出的是两点间的最短距离，则构造1->3 的路线是一定会构造出比2->3,则最终会造成总开销增大，贪心思想就构造出1->2->3的路径。

则上图不妨设1->2为d1,2->3为d2

则开销为d1-d1+d2-d2+d2-d1;

接下来变成四个点会发生什么，如下图

则我们的最小开销增加的是粉色线对应的距离 不妨设置3->4的距离为d3

则增加的开销为d3-d3+d3-d2+d2-d1;

下面给出五个点
d4-d4+d4-d3+d4-d2+d4-d1;

整理上面式子可以发现每次增加一个新的点
d2
d3+d3-d1
d4+d4-d2+d4-d1

=3d4+2d3-0d2-2d1

不妨再增加一个点

d5+d5-d3+d5-d2+d5-d1+(3d4+2d3-0d2-2d1)

=4d5+3d4+d3-d2-3d1

可以看出推导公式为
(n-1)dn+(n-2)dn-1+(n-2-2)dn-2+…+(n-2-2*k)dn-2-k+…

即最终所求，变为代码即可

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, t;
long long  a[N];
int main()
{
	cin >> t;
	while (t--)
	{
		cin >> n;
		for (int i = 0; i < n; i++) cin >> a[i];
		sort(a, a + n);
		if (n == 1 || n == 2) { cout << 0 << endl;
		continue;
		}
		else
		{
			long long ans = 0;
			ans -= (n - 2) * a[n - 1] + (n - 3) * a[n - 2];
			int k = n - 5;
			int m = n - 3;
			while (m)
			{
				ans -= k * a[m];
				m--;
				k -= 2;
			}
			cout << ans << endl;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34