【题目描述】给定一个单词,请问在单词中删除t个字母后,能得到的字典序最小的单词是什么?
【输入描述】输入的第一行包含一个单词,由大写英文字母组成。第二行包含一个正整数t。其中,单词长度不超过100,t小于单词长度。
【输出描述】输出一个单词,表示答案。
【思路分析】 在删除t个字母后字典序要最小,那么每一次删除一个字母后都保证当前得到的单词是字典序最小的,这样删除t个字母后得到的一定是字典序最小的,证明略。因此我们要做的就是每次删除一个字母时,遍历所有位置,选择一个最优的位置即可。
【AC代码】
#include<bits/stdc++.h>
using namespace std;
int main() {
string str, res = "", s1, s2;
int t;
cin >> str;
s1 = str;
s2 = str;
cin >> t;
for(int i = 0; i < t; i++) {
str.erase(str.begin()); //首先选择第一个位置
for(int j = 1; j < s2.size(); j++) {
s1.erase(s1.begin() + j); //删除第j个位置
if(s1 < str) {
str = s1;
}
s1 = s2; //记得复原
}
s2 = str; //删除完一个字母后复原
s1 = str;
}
cout << str;
return 0;
}
【问题描述】在很久很久以前,有n个部落居住在平原上,依次编号为1到n。第 个部落的人数为 。有一年发生了灾荒。年轻的政治家小蓝想要说服所有部落一同应对灾荒,他能通过谈判来说服部落进行联合。每次谈判,小蓝只能邀请两个部落参加,花费的金币数量为两个部落的人数之和,谈判的效果是两个部落联合成一个部落(人数为原来两个部落的人数之和)。
【输入描述】
输入的第一行包含一个整数n,表示部落的数量。第二行包含n个正整数,依次表示每个部落的人数。其中:
【输出描述】输出一个整数,表示最小花费。
【思路分析】要求最后总的花费最小,那么就让每次选的两个部落之和最小即可。
【AC代码】
#include<bits/stdc++.h>
using namespace std;
vector<int> a;
int n, t;
int main() {
cin >> n;
int sum = 0;
for(int i = 0; i < n; i++) {
cin >> t;
a.push_back(t);
}
sort(a.begin(), a.end()); //先排序
while(true) {
int temp = a[0] + a[1]; //选择前两个最小的
sum += temp;
a.erase(a.begin()); //删除前两个
a.erase(a.begin());
if(a.empty()) { //空了说明合并完成
break;
}else {
a.push_back(temp);
sort(a.begin(), a.end()); //记得排序
}
}
cout << sum;
return 0;
}