A過水，不講

題解 CF1077B 【Disturbed People】

• 這題就是個顯而易見的貪心可是我考場上差點沒想出來
• 顯然把一戶被打擾的人家的右邊人家的燈關掉肯定比把左邊的燈關掉
• 從左到右掃一遍，每次如果遇到一戶被打擾的人家就ans++，然后把它右邊的燈關掉
• 然后就做完了

# include <bits/stdc++.h>int a[101];int main() {int n;int ans = 0;scanf("%d", &n);for(int i = 1; i <= n; i++)scanf("%d", &a[i]);for(int i = 2; i <= n - 1; i++){if (a[i] == 0 && a[i - 1] == 1 && a[i + 1] == 1)ans++, a[i + 1] = 0;//關右邊的燈}printf("%d\n", ans);return 0; }

題解 CF1077C 【Good Array】

• 個人覺得這題比B還水
• 先排下序，掃一遍\(1-n\)
• 對于每個數\(i\)，如果\(i \neq n\)，則當\(\sum_{j=1}^na[j]-a[i]=2*a[n]\)時滿足條件
• 不然要是\(i = n\)的話，當\((\sum_{j=1}^na[j])-a[n]=2*a[n-1]\)時滿足條件
• 判斷一下就好了

# include <bits/stdc++.h># define ll long longstruct p {int id;ll x; };p a[200001];int cmp(p x, p y){return x.x < y.x;}std::vector<int> vec;int main() {int n;ll sum = 0;scanf("%d", &n);for(int i = 1; i <= n; i++)scanf("%d", &a[i].x), a[i].id = i, sum += a[i].x;std::sort(a + 1, a + n + 1, cmp);for(int i = 1; i <= n; i++){if(i != n)//情況1{if(sum - a[n].x - a[i].x == a[n].x)vec.push_back(a[i].id);}else //情況2{if (sum - a[n - 1].x - a[i].x == a[n - 1].x)vec.push_back(a[i].id);}}if(vec.size()){printf("%d\n", vec.size());for(int i = 0; i < vec.size(); i++)printf("%d ", vec[i]);}else printf("0");return 0; }

題解 CF1077D 【Cutting Out】

• 昨晚剛打的場，感觸深刻啊
• 昨天打的時候死命WA16結果才發現16是\(n=k\)的的點

• \(rp--,rating-=inf\)

• 好了說正事
• 這道題我們可以枚舉刪除次數，發現滿足單調性，果斷二分
• check掃一遍\(1-200000\)，對于每個數i，每次將序列長度加上(i出現的次數/當前check的刪除次數)，如果序列長度\(\ge k\)就return true;否則return false;

• 在二分時處理一下答案即可

• 其實用不著queue,但已經STL依賴癥了qwq

#include <bits/stdc++.h>int n, k; int a[200010], ans[200010]; int s[200010]; std::queue<int> st;int check(int x) {while(!st.empty())st.pop();for(int i = 1; i <= 200000; i++)for(int j = s[i] / x; j; j--)//能加的全部加進去st.push(i);if(st.size() >= k)//滿足條件{for(int i = 1; i <= k; i++)ans[i] = st.front(), st.pop();return true;}return false; }int main() {scanf("%d%d", &n, &k);for (int i = 1; i <= n; i++)scanf("%d", &a[i]), s[a[i]]++;int l = 0, r = 200001;while (l < r)//二分{int mid = (l + r + 1) >> 1;if (check(mid))l = mid;elser = mid - 1;}for (int i = 1; i <= k; i++)printf("%d ", ans[i]);return 0; }

轉載于:https://www.cnblogs.com/little-sun0331/p/9973962.html

總結

以上是生活随笔為你收集整理的Codeforces Round #521 (Div.3)题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。