TIOJ-1768

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

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

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

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

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

每個人的體重為ai

N2×107,ai20000


這題的N還真大(汗

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

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

時間複雜度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;
}
}