2021蓝桥杯模拟赛：删除字符串 && 谈判（贪心）

不念不忘少年蓝@ 2022-10-22 07:41 206阅读 0赞

## 删除字符串 ##

【题目描述】  
  给定一个单词，请问在单词中删除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。第i个部落的人数为 t i t\_\{i\} ti  
  
  有一年发生了灾荒。年轻的政治家小蓝想要说服所有部落一同应对灾荒，他能通过谈判来说服部落进行联合。

每次谈判，小蓝只能邀请两个部落参加，花费的金币数量为两个部落的人数之和，谈判的效果是两个部落联合成一个部落（人数为原来两个部落的人数之和）。

【输入描述】  
  输入的第一行包含一个整数n，表示部落的数量。

第二行包含n个正整数，依次表示每个部落的人数。

其中， 1 ≤ n ≤ 1000 , 1 ≤ t i ≤ 1 0 4 1 \\leq n \\leq 1000, 1 \\leq t\_\{i\} \\leq 10^4 1≤n≤1000,1≤ti≤104

【输出描述】  
  输出一个整数，表示最小花费。

【思路分析】  
  要求最后总的花费最小，那么就让每次选的两个部落之和最小即可。

【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;
    }