URAL 2026 Dean and Schedule 贪心、双端队列(deque)、队列(queue)

Source

UESTC 2016 Summer Training #17 Div.2

URAL 2026

My Solution

贪心， 双端队列、队列

先扫一遍记录各种字母出现的次数， 然后在扫一遍字母数组(从大到小)，依次记录没有出现过的字母

然后 扫一遍 分别记录奇数位置的'?' qo.push(i), 偶数位置的'?' qe.push(i) 同时如果'?'的个数 + 已经出现的种类数 < k 则 输出 -1

否则就可以了， 然后每次 if(26 - deq.front() > deq.back()) 来判断应该填优先填 minus的位置还是 plus的位置，(同时应该先判断是否容器为空)

具体见代码

复杂度 O(n)

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 8;

char val[maxn];
int letter[26];

deque deq;
queue qe, qo;
int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    //freopen("b.txt", "w", stdout);
    int T = 5;
    while(T--){
    #endif // LOCAL
    memset(letter, 0, sizeof letter);
    int k, len, sz = 0, cnte = 0, cnto = 0;
    scanf("%s", val);
    len = strlen(val);
    scanf("%d", &k);
    for(int i = 0; i < len; i++){
        if(val[i] != '?'){
            letter[val[i] - 'a']++;
            if(letter[val[i] - 'a'] == 1) sz++;
        }
        else{
            if(i&1) qe.push(i);
            else qo.push(i);
        }
    }
    cnte = qe.size(), cnto = qo.size();
    //cout<<cnte<<" "<<cnto<<endl;
    if(sz + cnte + cnto < k) printf("-1");
    else if(cnte + cnto == 0) printf("%s", val);
    else{
            //cout<<cnt<<endl; for(int j = 26 - 1; j >= 0; j--){
            if(letter[j] == 0) deq.push_back(j);
        }
        while(sz < k){ if(26 - deq.front() > deq.back()){
                if(!qe.empty()){
                    val[qe.front()] = (deq.back() + 'a');
                    deq.pop_back();
                    qe.pop();
                    sz++;
                }
                else{
                    val[qo.front()] = (deq.front() + 'a');
                    deq.pop_front();
                    qo.pop();
                    sz++;
                }
            }
            else{
                if(!qo.empty()){
                    val[qo.front()] = (deq.front() + 'a');
                    deq.pop_front();
                    qo.pop();
                    sz++;
                }
                else{
                    val[qe.front()] = (deq.back() + 'a');
                    deq.pop_back();
                    qe.pop();
                    sz++;
                }
            }
        }

        while(!qo.empty()){
            val[qo.front()] = 'z';
            qo.pop();
        }
        while(!qe.empty()){
            val[qe.front()] = 'a';
            qe.pop();
        }

        printf("%s", val);

    }
    #ifdef LOCAL
    printf("n");
    deq.clear();
    while(!qe.empty()) qe.pop();
    while(!qo.empty()) qo.pop();
    }
    #endif // LOCAL
    return 0;
}