A 牛半仙的妹子串

A 牛半仙的妹子串

预处理，将每个字符串最后的字母转化为数组下标，往数组里对应的结构体。最后查询即可。

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
const int N=1e6+10;
struct sa
{
    string s;
    int f;
    int id;
}a[N];
int n,m,k;
char x;
int cmp(const struct sa a , const struct sa b)
{
    if(a.f!=b.f) return a.f>b.f;
    else return a.id<b.id;
}
vector< sa > ans[27] ;// 结构体vector, ans[27]存26个英文字母的下标
int main()
{
    IOS;
    //freopen("data10.in","r",stdin);
    //freopen("w.txt","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].s>>a[i].f;
        a[i].id=i;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        ans[a[i].s[a[i].s.size()-1]-'a'].push_back(a[i]);
    }
    for(int i=1;i<=m;i++){
        cin>>x>>k;
        if(ans[x-'a'].size()<k) cout<<"Orz YYR tql"<<endl;
        else cout<<ans[x-'a'][k-1].s<<endl;
    }
    return 0;
}

另一种写法

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
const int N=1e6+10;
struct sa
{
    string s;
    int f;
    int id;
    bool operator <(const sa &a) const {//这里符号都是相反的
        if(a.f!=f) return a.f<f;
        else return a.id>id;
    }
}a[N];
int n,m,k;
char x;
vector< sa > ans[27];
int main()
{
    IOS;
    //freopen("data10.in","r",stdin);
    //freopen("w.txt","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].s>>a[i].f;
        a[i].id=i;
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        ans[a[i].s[a[i].s.size()-1]-'a'].push_back(a[i]);
    }
    for(int i=1;i<=m;i++){
        cin>>x>>k;
        if(ans[x-'a'].size()<k) cout<<"Orz YYR tql"<<endl;
        else cout<<ans[x-'a'][k-1].s<<endl;
    }
    return 0;
}

还是习惯这么写。

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
const int N=1e6+10;
struct sa
{
    string s;
    int f;
    int id;
    friend bool operator < (sa a, sa b){
        if(a.f!=b.f) return a.f>b.f;
        else return a.id<b.id;
    }
}a[N];
int n,m,k;
char x;
vector< sa > ans[27];
int main()
{
    IOS;
    //freopen("data10.in","r",stdin);
    //freopen("w.txt","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i].s>>a[i].f;
        a[i].id=i;
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        ans[a[i].s[a[i].s.size()-1]-'a'].push_back(a[i]);
    }
    for(int i=1;i<=m;i++){
        cin>>x>>k;
        if(ans[x-'a'].size()<k) cout<<"Orz YYR tql"<<endl;
        else cout<<ans[x-'a'][k-1].s<<endl;
    }
    return 0;
}