cf1553C. Penalty

題意：

有十輪點(diǎn)球，兩個(gè)隊(duì)伍輪流進(jìn)行，1表示進(jìn)，0表示不進(jìn)，？表示未知，如果比賽沒有了懸念將直接結(jié)束。現(xiàn)在讓你預(yù)測一個(gè)情況，使得進(jìn)行的輪數(shù)最少。裁判在決定停止點(diǎn)球階段時(shí)沒有考慮任何預(yù)測-你可能知道一些點(diǎn)球?qū)?huì)/不會(huì)得分，但裁判沒有。

題解：

當(dāng)時(shí)我第一反應(yīng)，最佳情況就是一方的？全是進(jìn)球，另一方？全沒進(jìn)球，為什么這樣，因?yàn)橐蟊荣惐M快結(jié)束，為了讓比賽沒有懸念，我們就要盡可能拉大比分，已有的0和1已經(jīng)確定了進(jìn)球情況，而？還是未知，所以我們將兩側(cè)？取相反，這樣就保證極端情況

代碼：

#include <bits/stdc++.h>using namespace std;int main() {int t;cin >> t;while (t--) {string s;cin >> s;int ans = 9;int cnt0 = 0, cnt1 = 0;for (int i = 0; i < 10; ++i) {if (i % 2 == 0) cnt0 += s[i] != '0';else cnt1 += s[i] == '1'; /*(10 - i) / 2表示如果第二個(gè)隊(duì)后面的點(diǎn)球全進(jìn)(9 - i ) / 2表示如果第一個(gè)隊(duì)后面的點(diǎn)球全進(jìn) */if (cnt0 > cnt1 + (10 - i) / 2) ans = min(ans, i);if (cnt1 > cnt0 + (9 - i) / 2) ans = min(ans, i);}cnt0 = 0, cnt1 = 0;for (int i = 0; i < 10; ++i) {if (i % 2 == 0) cnt0 += s[i] == '1';else cnt1 += s[i] != '0'; if (cnt0 > cnt1 + (10 - i) / 2) ans = min(ans, i);if (cnt1 > cnt0 + (9 - i) / 2) ans = min(ans, i);}cout << ans + 1 << endl;} }

總結(jié)

以上是生活随笔為你收集整理的cf1553C. Penalty的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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