Day 15

1.chika和蜜柑

chika和蜜柑
TopK、堆、排序

1.1 解析

1.2 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct Cmp
{
  bool operator()(const pair<int,int>& p1,const pair<int,int>& p2)
  {
      if(p1.first>p2.first)return true;
      else if(p1.first==p2.first&&p1.second<p2.second) return true;
      return false;
  }
};
int n,k;
int main()
{
    //输入样例
    cin>>n>>k;
    vector<int> s(n),t(n);
    for(int i=0;i<n;i++)cin>>s[i];
    for(int i=0;i<n;i++)cin>>t[i];
    //将甜度和酸度绑定
    vector<pair<int,int>> ts(n);
    for(int i=0;i<n;i++)
    {
        ts[i].first=t[i];
        ts[i].second=s[i];
    }
    //排序+降序
    sort(ts.begin(),ts.end(),Cmp());
    //统计前k个
    long long sumt=0,sums=0;
    for(int i=0;i<k;i++)
    {
        sumt+=ts[i].first;
        sums+=ts[i].second;
    }
    cout<<sums<<' '<<sumt;
    return 0;
}

2.对称之美

对称之美
字符串、哈希

2.1 解析

2.2 代码

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int t,n;
string s;
bool vis[110][26];//哈希表

bool check(int left,int right)
{
    for(int i=0;i<26;i++)
    {
        if(vis[left][i] && vis[right][i])return true;//该位置上必须出现过
    }
    return false;
}
int main()
{
    cin>>t;
    while(t--)
    {
        memset(vis,0,sizeof(vis));
        //输入数据
        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>s;
            //将字符串存入哈希表中
            for(auto& ch:s)
                vis[i][ch-'a']=true;
        }
        //判断是否回文
        int left=0,right=n-1;
        while(left<right)
        {
            if(!check(left,right))break;
            ++left,--right;
        }
        if(left>=right)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

3.添加字符

添加字符
字符串、枚举

3.1 解析

3.2 代码

#include <iostream>
using namespace std;
#include <string>
string a,b;
int main()
{
    cin>>a>>b;
    int m=a.size(),n=b.size();
    int ret=m;//记录不相等字符的个数
    for(int i=0;i<=n-m;i++)//枚举a的起始位置
    {
        int tmp=0;
        for(int j=0;j<m;j++)
        {
            if(a[j]!=b[i+j]) tmp++;
        }
        ret=min(ret,tmp);
    }
    cout<<ret<<endl;
    return 0;
}