每日两题cpp

• • 组队竞赛(贪心)
  • 删除公共字符(哈希)
  • 排序子序列(数组)
  • 倒置字符串(字符串)

解题思路

本题的主要思路是贪心算法，贪心算法其实很简单，就是每次选值时都选当前能看到的局部最解忧，所
以这里的贪心就是保证每组的第二个 是次大的 ；
先排好序，每次使用最左边的和最右边的两个进行组队，可以保证每队中间位置局部最大，对其加和;

#include
#include
#include
using namespace std;

int main()
{
    vectorarr;
    int n,tmp;
    while(cin>>n)
    {
        while(cin>>tmp)
        {
            arr.push_back(tmp);
        }
        //录入完成;
       
        sort(arr.begin(),arr.end());
        long long ret = 0;
        for(int i = n;i
            ret+=arr[i];
        }
        cout< 
删除公共字符(哈希) 
 
解题思路
 
 
 
搞个哈希表，存入要删的字符，遍历原字符串，用哈希表过滤的不需要的即可;
 
 
#include
#include
#include
#include
#include
#include
using namespace std;

int main()
{
    string s1,s2;
    unordered_setst;
    // 注意这里不能使用cin接收，因为cin遇到空格就结束了。
    // oj中IO输入字符串最好使用getline。
    getline(cin,s1);
    getline(cin,s2);

    for(int i = 0;i
        st.insert(s2[i]);
    }
    for(int i = 0;i
        if(st.find(s1[i])==st.end()) cout< 
排序子序列(数组) 
 
解题思路
 
 
 
flag作为标志转换器1为递增序列，-1为递减序列，每次变换完恢复0(待设置状态)，循环统计转折次数;
 
 
#include
using namespace std;

int main()
{
    int n;
    cin >> n;
    int arr[n];
    //当第一次出现子序列转折时，其实已经"一刀两断"，划分成两个子序列了
    int cnt = 1;
    int flag = 0;
    
    if (n <= 2) return 1;

    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    for (int i = 0; i < n; i++)
    {
        if (i + 1 < n && arr[i] < arr[i + 1])
        {
        	//flag待设置,根据递增还是递减设置flag;
            if (flag == 0) flag = 1;
			//flag-1递减状态，序列出现递增，划分，cnt++flag恢复初始待设置状态
            if (flag == -1)
            {
                flag = 0;
                cnt++;
            }
        }
        else if (i + 1 < n && arr[i] > arr[i + 1])
        {
            if (flag == 0) flag = -1;

            if (flag == 1)
            {
                cnt++;
                flag = 0;
            }
        }
        //else 这里就是arr[i] > arr[i + 1]，不处理只需要让i++ for里面处理了;
    }
    cout << cnt << endl;
    return 0;
}
 
倒置字符串(字符串) 

 解题思路
 
 
 
1.先反转每个单词;
 2.再反转整体字符串则可以达到目的;(善于观察)
 
 
#include
#include
#include
using namespace std;

int main()
{
    string str;
    vectorarr;
    getline(cin,str);
    int len = str.size();
    //先反转每个单词
    int l = 0;
    int r = 1;
    while(l
        while(r