TIOJ-1768

發表於 更新於 Disqus：

傳說中，P教授擁有一個蹺蹺板，叫作P-蹺蹺板。P-蹺蹺板是個長直且質量可忽略的板子，上面有$N$個等距的座位，編號為$0$到$N-1$，每個座位都只能坐一個人。特別的是，P-蹺蹺板的支點並不是固定的，使用者可以將支點架在任何一個座位的正下方。

如果支點左右的力矩相同，那麼蹺蹺板將會平衡。例如若$N=5$ ，五個座位上面的重量依序為$2,1,5,3,1$，若將支點架在$2$號座位下方，則左邊力矩$\ =2\times 2 + 1\times 1 = 3\times 1 + 1\times 2=\ $右邊力矩，故蹺蹺板會平衡。

有一天，P教授叫了$N$個人過來，請他們依序坐在P-蹺蹺板上，嘗試保持平衡。然而，由於每個人的體重不盡相同，而且支點沒辦法架在坐位之間，要找到平衡十分困難。

這時， P教授用他多年玩蹺蹺板的經驗，一眼看出了他們現在坐的順序有一個性質：至少存在一個$0\leq x<\max(1,\lfloor{\frac{N}{2}}\rfloor)$，使得如果把最前面$x$個人和最後面$x$個人交換，那麼一定可以找到一個支點使得蹺蹺板平衡。所謂把最前面個人和最後面個人交換，指的是鏡像交換，例如若$x=2$，代表把座位編號為$0$和$N-1$上面的人交換、座位編號為$1$和$N-2$上面的人交換；若$x=0$，代表完全不交換。

P教授把這個性質告訴了這$N$個人，決定考驗他們能不能將蹺蹺板平衡。給你每個位置目前坐的人的體重，你能幫助他們找到正確的交換方式與支點的位置嗎？

每個人的體重為$a_i$

$N\le 2\times 10^7, a_i\le 20000$

這題的$N$還真大(汗

先來整理一下式子吧。
假設我們把支點設在$t$，令$\sum a_i=S$。題目告訴我們左力矩=右力矩，把他們搬到同一邊，左力矩-右力矩=0，爆開他:
$$(\sum_{i=0}^{t}(t-i)a_i)-(\sum_{i=t+1}^{n-1}(i-t)a_i)=0$$
$$(\sum_{i=0}^{t}(t-i)a_i)+(\sum_{i=t+1}^{n-1}(t-i)a_i)=0$$
$$\sum_{i=0}^{n-1}(t-i)a_i=0$$
$$\sum_{i=0}^{n-1}t\times a_i=\sum_{i=0}^{n-1}i\times a_i$$
令等號右邊那陀為$res$
$$tS=res$$
$$t=\frac{res}{S}$$
多麼美妙的等式!
所以我們可以枚舉每個$x$，而因為交換是鏡像的，所以從$x$到$x+1$只需要交換兩項，也就只需要修改$res$四次，為常數時間。

一旦存在$x$滿足$res$可以被$S$整除，那就有答案了!

時間複雜度$\mathcal{O}(N)$

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
35
36
37
38
39
40
41
42
43
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
/*--------------------------------------------------------------------------------------*/

signed main() { EmiliaMyWife
	int n;
	cin >> n;
	vector<ll> arr(n);
	
	ll s = 0;
	for(int i = 0; i < n; i++)
		cin >> arr[i], s += arr[i];
	
	ll res = 0;
	for(int i = 0; i < n; i++)
		res += arr[i] * i;
	
	for(int i = -1; i < max(1, n / 2); i++) {
		if(~i) {
			res -= arr[i] * i;
			res -= arr[n - i - 1] * (n - i - 1);
			swap(arr[i], arr[n - i - 1]);
			res += arr[i] * i;
			res += arr[n - i - 1] * (n - i - 1);
		}
		if(res % s == 0)
			return cout << i + 1 << ' ' << res / s << '\n', 0;
	}
}