米哈游 10.16 笔试

#include<unordered_set>
#include<vector>
#include<iostream>
#include<algorithm>
#include<queue>
#include<utility>
#include<functional>
using namespace std;

//3，最多苹果
int main(){
    int N;
    cin>>N;
    vector<int> apple_num(N,0);
    vector<int> apple_last(N,0);
    for(int i=0;i<N;i++) cin>>apple_num[i];
    for(int i=0;i<N;i++) cin>>apple_last[i];
    //{left, expired date}
    priority_queue<pair<int, int>, vector<pair<int, int>>, function<bool( pair<int, int>&lhs,  pair<int, int>&rhs)>>  pq(
        [](const pair<int, int>&lhs,const pair<int,int>&rhs)->bool{
            return lhs.second>rhs.second;
        });
    int result=0;
    int i;
    //cout<<"start"<<endl;
    for(i=1;i<=N || !pq.empty();i++){
        while(!pq.empty() && pq.top().second<=i) pq.pop();
        if(pq.empty() &&i>N) break;
        //cout<<i<<","<<pq.size()<<endl;
        if(i<=N) pq.push({apple_num[i-1], i+apple_last[i-1]});
        result++;
        auto top=pq.top();
        pq.pop();
        if(--top.first>0){
            pq.push(top);
        }
    }
    cout<<result<<endl;
    return 0;
}


//2，找到 i<j<k st a[i]>a[k]>a[j]
int main(){
    int T,N;
    cin>>T;
    for(int t=0;t<T;t++){
        cin>>N;
        vector<int> nums(N,0);
        for(int i=0;i<N;i++) cin>>nums[i];
        bool result=false;
        int I=nums[0],J;
        bool find_first_j=false;
        for(int j=1;j<N;j++){
            if(nums[j]>I) I=nums[j];
            else{
                if(find_first_j){
                    if(nums[j]>J){
                        result=true;
                        break;
                    }else{
                        J=nums[j];
                    }
                }else{

                }
            }
        }
        cout<<(result?"Yes":"No")<<endl;
    }
    return 0;
}





//1,不超过m的最小sum
int main(){
    int M,N;
    cin>>N>>M;
    vector<int> cost(N,0);
    int result=0;
    for(int i=0;i<N;i++){
        cin>>cost[i];
        result+=cost[i];
    }
    unordered_set<int> s;
    s.insert(0);
    for(auto tmp:cost){
        vector<int> under_inserted;
        for(auto v:s){
            int temp=v+tmp;
            if(temp>=M){
                result=min(temp, result);
            }else{
                under_inserted.push_back(temp);
            }
        }
        for(auto v:under_inserted) s.insert(v);
    }
    cout<<result<<endl;
    return 0;
}