4.10 拼多多 笔试

第一次笔试，太菜了，希望大佬们指出问题给点经验，只刷题不思考不知道怎么优化，问题很大。
1.第一题 80%
思路是从大到小排序，每三个一买，不足三个，就原价买

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int N; 
    cin>>N;
    vector<int> price;
    for(int i=0;i<N;i++) {
        int temp;
        cin>>temp;
        price.push_back(temp);
    }
    //将原数组排序，从大到小，每三个一买，不足三个原价购买
    std::sort(price.begin(),price.end(),[&](const int& a,const int &b){return a>b;});
//    for(auto i:price) cout<<i<<" ";
    int ans=0;

    for(int i=0;i<N;){
        //i,i+1,i+2
        if(i+2<N){
            ans=ans+price[i]+price[i+1];
            i=i+3;
            continue;
        }
        else{
            ans+=price[i];
            i++;
        }
    }
    cout<<ans<<endl;
    return 0;
}

2.第二题 就对每个区间长度的求和，只过了20%

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
    int N,M;
    cin>>N>>M;
    vector<int> tree;
    for(int i=0;i<N;i++){
        int temp;
        cin>>temp;
        tree.push_back(temp);
    }
    int ans=0;
    //对于每个区间遍历
    vector<vector<int>> cc;
    for(int i=1;i<=N;i++){
        vector<int> ccc;
        for(int j=0;j<=N-i;j++){
            int sum=accumulate(tree.begin()+j,tree.begin()+j+i,0);
            ccc.push_back(sum);
            if(sum%M==0) ans++;
        }
        cc.push_back(ccc);
    }
    for(auto i:cc){
        for(auto j:i) cout<<j<<" ";
        cout<<endl;
    }
    cout<<ans<<endl;
    return 0;
}

3.第三题暴力回溯 只过了15%

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map> 
using namespace std;
set<string> numset;
void dfs(string s,int K, char a,int k){
    //返回条件
    if(k==K){
//        cout<<"find one"<<endl;
        numset.insert(s);
        return;
    }
    for(int i=0;i<s.size();i++){
       if(s[i]!=a){
            char temp=s[i];
            s[i]=a;
            dfs(s,K,a,k+1);
            s[i]=temp;
       }
    }

}

//返回损失的幸运值
int loss(string a,string b){
    int len=a.size();
    int res=0;
    for(int i=0;i<len;i++){
        int aa=a[i]-'0';
        int bb=b[i]-'0';
        res+=aa>bb?aa-bb:bb-aa;
    }
    return res;
}

int main(){
    int N,K;
    cin>>N>>K;
    //至少K个数字相同
    string num;
    for(int i=0;i<N;i++){
        char temp;
        cin>>temp;
        num+=temp;
    }
    //如何从当前的字符串出发得到中奖的字符串
    map<char,int> mp;//统计每个数字出现的次数
    for(auto i:num) mp[i]++;
    //回溯法遍历所有 k要求，t当前字符，当前字符现频率

    //将其他数字变成 它，损失的幸运值,

    for(auto i:mp){
        char t=i.first;
        string temp=num;
        //这里只能深搜，不一定时连续的
        dfs(num,K,i.first,i.second);
    }
    //对获取到的set进行遍历
    int minvalue=INT_MAX;
    string ans;
    for(auto i:numset){
        int temp=loss(num,i);
        if(temp<minvalue){
            ans=i;
            minvalue=temp;
        }
    }
    cout<<minvalue<<endl;
    cout<<ans<<endl;
//    if(INT_MAX==(1<<31-1)) cout<<"1111"<<endl;
    cout<<(1<<31)-1<<endl;
    return 0;
}

4.双指针 记录状态 60%

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<climits>
using namespace std;
int main(){
    int N,K;
    cin>>N>>K;
    vector<int> color;
    for(int i=0;i<N;i++) {
        int temp;
        cin>>temp;
        color.push_back(temp);
    }
    //双指针法
    int i=0,j=0;
    int ans=0;
    int k=0;//已经移去的方块的数量
    while(j<N){
        if(color[i]==color[j]&&j<N) {
            j++;
        }

        else{
            if(k<K){k++;j++;}
            else {
                cout<<j<<" "<<i<<" "<<K<<endl;
                ans=max(ans,j-1-i+1-K);
                k=0;
                i++;
                j=i;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}