2022年6月13日16:25:17
A. Parkway Walk
题目大意：
你正在穿过你家附近的公园大道。公园路有 n+1 个长椅，从左到右从 1 到 n+1 编号。长凳 i 和 i+1 之间的距离是 ai 米。
最初，你有 m 个单位的能量。要走 1 米的距离，您需要消耗 1 个单位的能量。如果你没有精力，你就不能走路。此外，您可以坐在长凳上恢复能量（这是恢复能量的唯一方法）。当你坐着时，你可以恢复任何你想要的整数能量（如果你坐得更久，你会恢复更多的能量）。请注意，您的能量可以超过 m。
你的任务是找到你必须恢复的最小能量（通过坐在长凳上）从长凳 1 到达长凳 n+1（并结束你的步行）。
你必须回答 t 个独立的测试用例。
输入
输入的第一行包含一个整数 t (1≤t≤100) — 测试用例的数量。然后是 t 个测试用例。
测试用例的第一行包含两个整数 n 和 m（1≤n≤100；1≤m≤10^4）。
测试用例的第二行包含 n 个整数 a1,a2,…,an (1≤ai≤100)，其中 ai 是长凳 i 和 i+1 之间的距离。
输出
对于每个测试用例，打印一个整数——在相应的测试用例中，从长凳 1 到达长凳 n+1（并结束步行）所需恢复的最小能量（通过坐在长凳上）。
inputCopy
3
3 1
1 2 1
4 5
3 3 5 2
5 16
1 2 3 4 5
outputCopy
3
8
0
题解：
对距离求和，减去初始值，即得到答案。
void solve(){
int n, k;
cin >> n >> k;
ll sum = 0;
for (int i = 0; i < n;i++){
int x;
cin>>x;
sum += x;
}
cout << max(sum - k,0ll) << nl;
}
B. Promo
题目大意：
商店出售 n 件商品，第 i 件商品的价格为 pi。商店管理层将举行促销活动：如果顾客至少购买 x 件商品，则其中最便宜的 y 件是免费的。
管理层尚未决定 x 和 y 的确切值。因此，他们要求您处理 q 个查询：对于给定的 x 和 y 值，如果客户进行一次购买，则确定免费收到的物品的最大总价值。
请注意，所有查询都是独立的；它们不会影响商店的库存。
输入
第一行包含两个整数 n 和 q (1≤n,q≤2?10^5)——分别是商店中的商品数量和查询次数。
第二行包含 n 个整数 p1,p2,…,pn (1≤pi≤10^6)，其中 pi — 第 i 件商品的价格。
以下 q 行分别包含两个整数 xi 和 yi (1≤yi≤xi≤n) — 第 i 个查询中参数 x 和 y 的值。
输出
对于每个查询，打印一个整数——一次购买免费收到的物品的最大总价值。
inputCopy
5 3
5 3 1 5 2
3 2
1 1
5 3
outputCopy
8
5
6
题解：
贪心：排序后取最大的 xi 件衣服中偏小的 yi 件的价值和。
注意暴力会超时，选择前缀和O(1)的时间解决问题。
不开 long long 毁一生
void solve(){
int n, q;
cin >> n >> q;
int p[n+1] = {0};
for (int i = 0; i < n;i++)
cin >> p[i];
sort(p, p + n);
ll sum[n + 1] = {0};
sum[1] = p[0];
for (int i = 2; i <= n;i++)
sum[i] = sum[i - 1] + p[i - 1];
while(q--){
int a, b;
cin >> a >> b;
cout << sum[n - a + b] - sum[n - a] << nl;
}
}
C. awoo’s Favorite Problem
题目大意：
给定两个长度为 n 的字符串 s 和 t。两个字符串中的每个字符都是“a”、“b”或“c”。
在一个动作中，您可以执行以下操作之一：
选择 s 中出现的“ab”并将其替换为“ba”；
选择 s 中出现的“bc”并将其替换为“cb”。
您可以执行任意数量的移动（可能为零）。你能改变字符串 s 使它等于字符串 t 吗？
输入
第一行包含一个整数 q (1≤q≤10^4)——测试用例的数量。
每个测试用例的第一行包含一个整数 n (1≤n≤10^5)——字符串 s 和 t 的长度。
第二行包含长度为 n 的字符串 s。每个字符是“a”、“b”或“c”。
第三行包含长度为 n 的字符串 t。每个字符是“a”、“b”或“c”。
所有测试用例的 n 总和不超过 10^5。
输出
对于每个测试用例，如果您可以通过执行任意数量的移动（可能为零）来更改字符串 s 以使其等于字符串 t，则打印“YES”。否则，打印“否”。
inputCopy
5
3
cab
cab
1
a
b
6
abbabc
bbaacb
10
bcaabababc
cbbababaac
2
ba
ab
outputCopy
YES
NO
YES
YES
NO
题解：
字符串处理，按照题意的处理方式进行分类讨论，具体见代码：
bool check(string &a,int i,int n,char b,char c){
if(i + 1 >= n)
return 0;
for (int j = i + 1; j < n; ++j) {
if(a[j] == b)
continue;
else if(a[j] == c) {
swap(a[i], a[j]);
return 1;
} else {
return 0;
}
}
}
void solve(){
int n;
string a, b;
cin >> n >> a >> b;
bool flag = 1;
for (int i = 0; i < n && flag; ++i) {
if(a[i] != b[i]) {
if(a[i] == 'b' && b[i] == 'c')
flag = check(a, i, n,'b','c');
else if(a[i] == 'a' && b[i] == 'b')
flag = check(a, i, n,'a','b');
else
flag = 0;
}
}
if(a != b)
flag = 0;
if(flag)
cout << "yes" << nl;
else
cout << "no" << nl;
}
|