CF1261B1 Optimal Subsequences (Easy Version)

题意:求字符串中取k长度的子序列使总数最大,并且字典序最小

题解:首先易知子序列总数最大肯定要在字符串中取出k个最大的数组成子序列,只需要将字符串排序后把最大的k个数存入一个数组,但是本题难点在于要求字典序最小的子序列,比如 10 20 20 是答案而 20 10 20不是答案

即使他们的总数一样大。因此要想办法提取出来

我们有这样一个猜测,要考虑k个数当中最小的那个数就可以,打个比方,10 20 30 20 30 40中取四个数,那么所有大于20的数都会被存进来,所以不需要考虑顺序,只需要把他们全部存进来就可以

而20则需要考虑将第一个20存入,因此记录k个数当中最小的数有cnt个,然后对原字符串从头枚举,将最前面cnt个最小数存进来,如果遇到的数大于最小数,直接存入即可

代码如下:

CF1261B1 Optimal Subsequences (Easy Version)
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int N=2e5+10;
int a[N];
int b[N];
int main(){
    int n;
    int t;
    
    
        cin>>n;
        int i;
        for(i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        int m;
        cin>>m;
        memcpy(b,a,sizeof a);
        sort(b,b+n);
        reverse(b,b+n);
        while(m--){
        int k,pos;
        cin>>k>>pos;
        int sign=b[k-1];
        int flag=1;
        for(int j=k-2;j>=0;j--){
            if(b[j]==b[k-1])
            flag++;
            else
            break;
        }
        vector<int> num;
        
        for(i=0;i<n;i++){
            if(a[i]>sign)
            num.push_back(a[i]);
            if(a[i]==sign&&flag){
                num.push_back(a[i]);
                flag--;
            }
        }
        cout<<num[pos-1]<<endl;
        
        }
    
    
}
View Code

 

上一篇:CF685C Optimal Point


下一篇:[bzoj4094]Optimal Milking