Educational Codeforces Round 130 (Rated for Div. 2)

A. Parkway Walk 题目描述

求走完所有距离所需最小的补充能量数

题目分析

用所需总能量数减去初始能量即可

code #include<bits/stdc++.h> using namespace std; int n, m, k, t; void solve() { int sum = 0; cin >> n >> m; for(int i = 0; i < n; i ++) { int u; cin >> u; sum += u; } if(sum <= m)puts("0"); else cout << sum - m << "\n"; } int main() { cin >> t; while(t --) solve(); return 0; } B. Promo 题目描述

如果顾客购买了至少 x 件商品，最便宜的y件商品都是免费的。对于每次询问求各科可以免费获得商品的最大价值

题目分析

用贪心的思维则我们尽可能选择大的，这样能使得其中y个较小的值最大化。对于所免费获得的价值，我们可以用前缀和来计算，从而达到降低时间复杂度的目的

code #include<bits/stdc++.h> using namespace std; const int N = 2e5 + 10; typedef long long ll; int n, m, k, t; ll a[N], s[N]; bool cmp(int a, int b) { return a > b; } int main() { cin >> n >> t; for(int i = 1; i <= n; i ++)cin >> a[i]; sort(a + 1, a + n + 1, cmp); for(int i = 1; i <= n; i ++) { s[i] = s[i - 1] + a[i]; //cout << s[i] << "---\n"; } while(t --) { int x, y; cin >> x >> y; cout << s[x] - s[x-y] << "\n"; } return 0; } C. awoo’s Favorite Problem 题目描述

问字符串a能否通过两种操作变成b: 操作1（将 ab 变成 ba） 操作2（将 bc 变成 cb）

题目分析

两个操作的共性都是通过b来改变字母的相对位置，我们首先可以去掉两个字符串当中的b,若得到的字符串不相等则一定无法完成变换

此外根据观察可以发现，a的位置只能向后移动，c的位置只能向前。所以在字符串a中的字符a位置一定小于等于在字符串b 中的，字符c的情况相反

通过以上两部分判断即可

code #include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int n, m, k, t; void solve() { int a[N] = {0}, b[N] = {0}, a1[N] = {0}, b1[N] = {0}; int co1 = 0, co2 = 0, co3 = 0, co4 = 0; string s, r, s1, r1; s1.clear(), r1.clear(); cin >> n >> s >> r; for(int i = 0; i < n; i ++) { if(s[i] != 'b') s1 += s[i]; if(s[i] == 'a') a[co1 ++] = i; if(s[i] == 'c') b[co2 ++] = i; if(r[i] != 'b') r1 += r[i]; if(r[i] == 'a') a1[co3 ++] = i; if(r[i] == 'c') b1[co4 ++] = i; } //cout << s1 << "--" << r1 << "\n"; if(s1 != r1) puts("NO"); else { for(int i = 0; i < co1; i ++) { if(a[i] > a1[i]) { puts("NO"); return; } } for(int i = 0; i < co2; i ++) { if(b[i] < b1[i]) { puts("NO"); return; } } puts("YES"); } } int main() { cin >> t; while(t --) solve(); return 0; }

---

1.本站遵循行业规范，任何转载的稿件都会明确标注作者和来源；2.本站的原创文章，会注明原创字样,如未注明都非原创，如有侵权请联系删除！；3.作者投稿可能会经我们编辑修改或补充；4.本站不提供任何储存功能只提供收集或者投稿人的网盘链接。