鏈接：

http://codeforces.com/contest/798/problem/D

題意：

給你兩個長度為n的數(shù)列a和b，讓你選n/2+1個下標，使得2*∑ai>suma,2*∑bi>sumb

題解1：

用一個叫random_shuffle的東西，每次都亂選，然后暴力前n/2+1個。

這種做法真的是毫無人性啊。以后不會的就這么辦吧

代碼：

31 ll a[MAXN], b[MAXN], c[MAXN]; 32 33 int main() { 34 ios::sync_with_stdio(false); 35 int n; 36 cin >> n; 37 rep(i, 0, n) c[i] = i; 38 ll suma = 0, sumb = 0; 39 rep(i, 0, n) cin >> a[i], suma += a[i]; 40 rep(i, 0, n) cin >> b[i], sumb += b[i]; 41 while (1) { 42 random_shuffle(c, c + n); 43 ll A = 0, B = 0; 44 rep(i, 0, n / 2 + 1) A += a[c[i]], B += b[c[i]]; 45 if (2 * A > suma && 2 * B > sumb) break; 46 } 47 cout << n / 2 + 1 << endl; 48 rep(i, 0, n / 2 + 1) cout << c[i] + 1 << ' '; 49 return 0; 50 }

?

題解2：

首先注意到，選出n / 2 + 1個數(shù)，2倍的和大于總和，等價于選出n / 2 + 1個數(shù)，總和大于剩下的數(shù)。

因為可以取n / 2 + 1個，那么先對A排序，B不動，先把A[1]選了（這個是用在證明A數(shù)組成立用的），A【1】是當前A中最大的了。當然了也選了一個B，就是選了B[A[1].id]，

然后每兩個做一pair，選一個比較大的B，也就是max(B[A[i].id], B[A[i + 1].id])

這樣，B數(shù)組是滿足的，這很容易證明，因為沒一對中，都選了一個較大的。然后加上第一個，總和肯定大于剩下 的。

也就是

max(b[1], b[2]) >= min(b[1], b[2])

max(b[3], b[4]) >= min(b[3], b[4])

max(b[5], b[6]) >= min(b[5], b[6])

那么全部相加，不等號方向不變。而且開頭還有一個b[A[1].id]加了進來，所以是嚴格大于的。

?

再來看看A的證明。

第一是選了a[1]

然后選a[2]和a[3]的那個呢？不固定的，還要看B，但是不管，有以下不等式。

a[1] >= any(a[2], a[3])

any(a[2], a[3]) >= any(a[4], a[5])

any(a[4], a[5]) >= any(a[5], a[6])

也就是，你選了一個a[1]，然后a[2]和a[3]選那個是沒關(guān)系的，可以用a[1]和它比較，然后又因為選了any(a[2], a[3])，那么你a[4]和a[5]選那個是沒所謂的，因為可以用any(a[2], a[3])和它比較。

最后，any(a[n - 1], a[n]) > 0，所以是嚴格大于的。

代碼：

31 struct Node { 32 int id, a, b; 33 bool operator <(const Node &t) const { 34 return a > t.a; 35 } 36 }p[MAXN]; 37 38 int main() { 39 ios::sync_with_stdio(false); 40 int n; 41 cin >> n; 42 VI ans; 43 rep(i, 0, n) p[i].id = i; 44 rep(i, 0, n) cin >> p[i].a; 45 rep(i, 0, n) cin >> p[i].b; 46 sort(p, p + n); 47 ans.pb(p[0].id); 48 for (int i = 1; i < n; i += 2) { 49 int t = p[i].id; 50 if (p[i].b < p[i + 1].b) t = p[i + 1].id; 51 ans.pb(t); 52 } 53 cout << ans.size() << endl; 54 rep(i, 0, ans.size()) cout << ans[i] + 1 << ' '; 55 return 0; 56 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/baocong/p/6783227.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的Codeforces Round #410 (Div. 2) D. Mike and distribution 思维+数学的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。