[BZOJ 1029]建筑抢修

danihao123 posted @ 2016年8月25日 09:54 in 题解 with tags BZOJ JSOI 省选 贪心 排序 , 878 阅读
转载请注明出处:http://danihao123.is-programmer.com/

废了。

我彻底废了。

就一个贪心水体。按截止时间排序然后遍历,当前花时间能干完就干,不能的话看能不能把更劣的选择换。仅此而已。

代码:

/**************************************************************
    Problem: 1029
    User: danihao123
    Language: C++
    Result: Accepted
    Time:396 ms
    Memory:2764 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
const int maxn=150001;
struct Node{
    int a,b;
    bool operator <(const Node& x) const{
        return b<x.b;
    }
    bool operator >(const Node& x) const{
        return b>x.b;
    }
};
Node T[maxn];
priority_queue<ll> Q;
int main(){
    int n;
    register int i,ans=0;
    register ll cur=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d%d",&T[i].a,&T[i].b);
    sort(T+1,T+1+n);
    for(i=1;i<=n;i++){
        if(cur+T[i].a<=T[i].b){
            cur+=T[i].a;
            Q.push(T[i].a);
        }else{
            if(Q.size() && Q.top()>T[i].a){
                cur-=Q.top();
                Q.pop();
                cur+=T[i].a;
                Q.push(T[i].a);
            }
        }
    }
    printf("%d\n",Q.size());
    return 0;
}
scholarship-fellows 说:
Jul 05, 2023 08:28:30 PM

Scholarship-fellowship works on giving out better service in different forms and we do not sell or giveaway your personal information other than public info giving out by you. We are very conscious about mail spam and we try to protect every email as much as possible. In certain cases your scholarship-fellowship.com mail may be exposed to public. Scholarship-fellowship works on giving out better service in different forms and we do not sell or giveaway your personal information.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter