pdd笔试第三四题ac题解(nlgn)

第四题一开始一直是10% 最后一分钟马上放弃了突然发现少了个条件然后填上就a了

主要思路是离散化+滑动窗口

首先发现颜色数量有那么点点大如果按照从c[i]进行遍历铁定超时所以采用map进行一次离散化

同时建立一个vector数组的数组 vect[i]存的形式为a0 b0 a1 b1 a2 b2 a3，其中ax表示有连续 ax 个 i 颜_色，[放和谐] bx表示 ax- 1到 ax 之间的与i不同的颜色的个数
发现是不是有些过于意识流我来举一个例子
对于
1 12 3 1 12 3 1 12 3
这种输入通过map离散能将原输入变为
0 1 2 0 1 2 0 1 2
之后对于vect数组
vect[0] 1 2 1 2 1 代表首先连续出现了一个0 之后与下一个0距离为2 之后又连续出现了一个0 之后与下一个距离还为2 之后又连续出来了一个0
所以
vect[1]也是 1 2 1 2 1 简单分析便可知道我们不用存储每个元素与开始或结束位置的距离
所以在本样例中 vect[0] = vect[1] = vect[2]
粗略分析一下时间复杂度每次遍历到一个元素至多会向整个vec数组中添加两个元素一个向这个元素对应的位置添加与上个相同元素的间隔一个向前一位元素添加连续出现的次数
之后在对每个颜色进行滑动窗口时
数组中每个元素至多被访问两遍
因此数组每个元素至多被遍历四遍
而离散的消耗是O(nlogk) k为元素的取值个数
针对题目要求k <= n
因此算法的总复杂度是O(nlogn)
很符合1e5的数据规模
至于如何在这种奇葩的数组中进行滑动窗口我觉得还是比较好想的就不继续说了
本题数据应该挺水的O(n^2)的复杂度也能混过去

#include <iostream>
#include <map>
#include <vector>
#include <cstring>
#define maxn 100001
using namespace std;
int cnt = 0;
int asd[maxn];
int yuan[maxn];
vector<int>vec[maxn];
int ls[maxn];
int main() {
    memset(ls,-1,sizeof(ls));
    int n,k;
    cin >> n >> k;
    map<int, int>see;
    for(int i = 0; i < n; i++){
        int t;
        cin >> t;
        auto ite = see.find(t);
        if(ite == see.end()){
            see[t] = cnt++;
        }
        asd[i] = see[t];
    }
    int pre = asd[0],siz = 1;
    ls[asd[0]] = 0;
    for(int i = 1; i < n; i ++){
        if(pre != asd[i]){
            if(ls[asd[i]] != -1){
                //cout << asd[i] <<" " <<i - ls[asd[i]] - 1 << endl;
                vec[asd[i]].push_back(i - ls[asd[i]] - 1);
            }
            vec[pre].push_back(siz);
            ls[asd[i]] = i;
            //cout<<pre << " "<<siz<<endl;
            pre = asd[i];
            siz  = 1;
        }else{
            ls[asd[i]] = i;
            ++siz;
        }
    }
    vec[pre].push_back(siz);
    int maxx = 0;
    for (int i = 0; i < cnt; ++i) {
        vector<int>& e = vec[i];
        int siz = e.size();
        int r = 0;
        int p = 0;
        int temp = e[0];
        for(int j = 0; j < siz; j+=2){
            if(r < j){
                r = j;
                temp = e[j];
                p = 0;
            }
            while(p < k && r != siz-1){
                if(p + e[r+1] <= k){
                    temp += e[r+2];
                    p+=e[r+1];
                    r += 2;
                }else
                break;
            }
            if(temp > maxx)
            maxx = temp;
            if(r > j){
                p -= e[j+1];
                temp -= e[j]; 
            }
        }
    }
    cout << maxx;
}

第三题思路就很直观了我觉得看看代码就能懂就不分析了

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
int k[10];
int main(){
    int n,tb;
    cin >> n >> tb;
    string t;
    cin >> t;
    for(int i = 0; i < n; i++){
        ++k[t[i]-'0'];
    }
    int minn = 999999999;
    int c = -1;
    for(int i = 0; i < 10; i++){
        int temp = 0;
        int tc = tb - k[i];
        for(int j = 1; j < 10; j++){
            if(tc <= 0)
            break;
            if(i-j >= 0){
                int p = min(k[i-j],tc);
                tc -= p;
                temp += p*j;
            }
            if(tc == 0)
            break;
            if(i+j < 10){
                int p = min(k[i+j],tc);
                tc -= p;
                temp += p*j;
            }
            if(tc == 0)
            break;
        }
        //cout << temp << " " << i <<endl;
        if(minn > temp) {
            minn = temp;
            c = i;
        }
    }
    int b = tb -k[c];
    for(int i = 1; i < 10; i++){
        if(b <= 0)
        break;
        if(c + i  < 10){
            for(int j = 0; j <= n-1 && b > 0; j++){
                if(t[j] == '0'+c+i){
                    t[j] = '0'+c;
                    b--;
                }
            }
        }
        if(b <= 0)
        break;
        if(c - i  >= 0){
            for(int j = n-1; j >= 0 && b > 0; j--){
                if(t[j] == '0'+c-i){
                    t[j] = '0'+c;
                    b--;
                }
            }
        }

    }
    cout << t;
}

#拼多多笔试##拼多多##笔试题目#