字节一道笔试题记录

opencode

发布于 2022-12-26 15:51:59

1420

发布于 2022-12-26 15:51:59

文章被收录于专栏：知识同步

优先队列和dp

简单说就是

输入一个有序整数数组，依次访问每个数，可以取或者不取，但是每次取必须保证所有取得的数之和大于等于0，求最多可以取几个数。

#include <priority_queue>
#include <iostream>

using namespace std;

int main(){
    int t;
    cin>>t;

    for(int i=0;i<t;i++){
        int n;
        cin>>n;

        vector<int> nums;

        for(int j=0;j<n;j++){
            int temp;
            cin>>temp;
            nums.push_back(temp);
        }

        priority_quque<int, vector<int>, greater<int>> q;
        int sum=0;
        for(auto item:nums){
            sum+=item;
            q.push(item);
            while(sum<0){
                sum-=q.front();
                q.pop();
            }
        }

        cout<<q.size();

    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021-09-12，如有侵权请联系 cloudcommunity@tencent.com 删除