Acwing——第79场周赛
第一题
存在一个数列 a 1 a_1 a1, a 2 a_2 a2, a 3 a_3 a3…，其中 a i a_i ai=1+2+…+i。
给定一个整数 n，请你判断是否存在一个数列中的元素 a i a_i ai 恰好等于 n。
输入格式
一个整数 n。
输出格式
如果满足条件的数列元素存在，则输出 YES，否则输出 NO。
数据范围
前 4 个测试点满足 1≤n≤4。
所有测试点满足 1≤n≤500。
输入样例1：
1
输出样例1：
YES
输入样例2：
2
输出样例2：
NO
输入样例3：
3
输出样例3：
YES
分析：由于n最大是500，所以直接暴力枚举就行。循环枚举 a i a_i ai，如果 a i a_i ai = n就打印YES ; 否则当 a i a_i ai > n时，退出循环，打印NO。
代码：
#include<iostream>
using namespace std;
int main(){
int n;
scanf("%d",&n);
int sum = 0;
bool ok = false;
for(int i = 1;i <= n;i++){
sum += i;
//sum == n 说明有答案
if(sum == n){
ok = true;
break;
}
//sum > n 直接退出循环
if(sum > n) break;
}
if(ok) puts("YES");
else puts("NO");
return 0;
}
第二题
给定一个队列，初始时队列为空。
首先，依次从队尾插入 a、b、c、d、e 五个元素。
随后，不断重复以下操作：
设当前队头元素为 x。
依次从队尾插入两个 x。
将队头元素 x 弹出队列。
例如，第 1 轮操作过后，队列变为 b、c、d、e、a、a，第 1 个被弹出队列的元素为 a；第 2 轮操作过后，队列变为 c、d、e、a、a、b、b，第 2 个被弹出队列的元素为 b；第 3 轮操作过后，队列变为 d、e、a、a、b、b、c、c，第 3 个被弹出队列的元素为 c…
请你计算并输出第 n 个被弹出队列的元素。
输入格式
一个整数 n。
输出格式
输出第 n 个被弹出队列的元素。
数据范围
前 5 个测试点满足 1≤n≤10。
所有测试点满足 1≤n≤109。
输入样例1：
1
输出样例1：
a
输入样例2：
6
输出样例2：
a
分析：
最开始队列中有a b c d e共5个元素，队头每弹出一个元素，队列尾都会加入两个相同的元素。
初始队列：a,b,c,d,e
弹出前五个元素：a,a,b,b,c,c,d,d,e,e
弹出前十个元素：a,a,a,a,b,b,b,b,c,c,c,c,d,d,d,d,e,e,e,e
弹出前二十个元素：…
我们发现每经过一轮，队列里的元素数量都要翻倍（初始是5）。那么我们就可以先求出输入的 n 是属于哪一轮的。假设 n 属于第 i 轮，第 i 轮的队列元素数量为 len。那么 n 减去 前 i - 1轮元素数量总和
就是在第 i 轮中的位置。此时的一个元素的数量为 cnt = len / 5，接着我们在对其上取整等到的就是答案,还需要将其转为字符。
例如n = 46。
n > s 1 s_1 s1 = 5
n > s 2 s_2 s2 = 5 + 10
n > s 3 s_3 s3 = 5 + 10 + 20;
n < s 4 s_4 s4 = 5 + 10 + 20 + 40;
n -= s 3 s_3 s3 (n = 11)
此时队列中一个元素的个数为 cnt = len / 5 = 40 / 5 = 8;
我的答案为: ans =（n + cnt - 1）/ cnt (ans = 2)
最终答案还需要将其转为字符 (char)(‘a’ + ans - 1)
最终的答案就为 b
代码：
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n;
scanf("%d",&n);
int s = 0,k = 5;
while(s + k < n){
s += k;
k *= 2;
}
n -= s;
int cnt = k / 5;
//上取整
int ans = (n+cnt-1)/cnt;
cout<<(char)(ans -1 + 'a')<<'\n';
return 0;
}
第三题
某地区的车牌号由 n 位数字组成。
如果一个车牌号中包含至少 k 个相同的数字，那么这个车牌号就被称为靓号。
如果车主对自己的车牌号感到不满意，还可以花钱对其进行修改。
每修改其中的一位数字，所需花费的具体金额为该位上修改前数字与修改后数字之差的绝对值。
例如，设车牌号为 0100，将其中的第 2 位数字从 1 修改为 3，使得车牌号变为 0300，所需花费的金额为 |1−3|=2。
现在，给定一个车牌号，请你花费最小的金额，将其修改为一个靓号。
输出最小花费金额以及得到的靓号。
如果最小花费下可以得到的靓号不唯一，则优先选择字典序最小的那个。
输入格式
第一行包含两个整数 n,k。
第二行包含一个长度为 n 的由数字（0∼9）组成的字符串。
输出格式
第一行输出所需花费的最小金额。
第二行输出最小花费下可以得到的靓号，如果不唯一，则输出字典序最小的那个。
数据范围
前 5 个测试点满足 2≤n≤10。
所有测试点满足 2≤n≤ 1 0 4 10^4 104，2≤k≤n。
输入样例1：
6 5
898196
输出样例1：
4
888188
输入样例2：
3 2
533
输出样例2：
0
533
输入样例3：
10 6
0001112223
输出样例3：
3
0000002223
分析:
第一题可以通过，依次枚举，将原串s中的k个字符分别变为 ‘0’,‘1’,‘2’,…‘9’，所有所需要的代价取一个最小值，即可得到答案。
第二题求解字典序最小，我们只需要保证，本轮循环枚举的字符是 c 时：
1.先将原串中大于 c 的字符，从最小的字符开始变为 c
2.每次将原串中小于 c 的字符，从最大的字符开始变为 c
注意：我们可以定义一个大小为19的vector，分别记录大于 c 的字符下标，和小于c的字符下标
0 ~ 9 映射 小于字符c 的字符下标（这里的字符下标是在在原串中的字符下标）
10 ~ 18 映射 大于字符c的字符下标
举例:字符 c = ‘3’时,
字符 0 的下标就为 (‘0’ - ‘3’ + 9) = 6
字符4的下标就为(‘4’ - ‘3’ + 9) = 10
代码：
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
int n,k;
string s,ans;
int low_cost = 1e9;
void solve(char x){
//映射下标 -9 ~ 9
vector<int> p[19];
将s中所有的字符分别映射到p中对应的位置中
for(int i = 0;i < n;i++){
p[s[i] - x + 9].push_back(i);
}
string ss = s;
int cnt = 0,cost = 0;
// i 是代价
for(int i = 0;cnt < k;i++){
//我们优先将原串中大于 字符 x 的字符变为x 这样的目的是让最终的字典序最小
for(int j = 0;j < p[9+i].size() && cnt < k;j++){
cost += i;
cnt++;
ss[p[9+i][j]] = x;
}
//i > 0 的原因是，上面已经统计过代价为0的情况了，代价为0的情况只需要统计一次
if(i){
for(int j = p[9-i].size()-1;j >= 0 && cnt < k;j--){
cost += i;
cnt++;
ss[p[9-i][j]] = x;
}
}
}
if(cost < low_cost || (cost == low_cost && ss < ans)){
low_cost = cost;
ans = ss;
}
}
int main(){
scanf("%d%d",&n,&k);
cin>>s;
for(int i = 0;i < 10;i++){
solve('0' + i);
}
cout<<low_cost<<'\n';
cout<<ans<<'\n';
return 0;
}