UVa1153 Keep the Customer Satisfied [贪心]

ajcxsu
ajcxsu 2018年06月18日
  • 23 次阅读

傻逼题不会系列

Problem

给n个需要t时间完成的工作
每个工作必须要在ei时间前完成
问最多能完成多少个工作

多组数据
输出中每组数据之间有一个空行(??)

Solution

被shabi输出坑了挺久
然而并不会这道题

对于现在的方案,如果要加入一个工作但没法加入,有三种操作可选:

  1. 交换完成工作序列
  2. 替代一个工作
  3. 放弃这个工作

如果我们给加入时间排个序,那么第一个操作就可以免了,因为无论怎么交换都无法加入这个工作
所以只剩替代一个工作或者放弃。
当然是替代所耗时间最长的工作。
后方的所有工作都会左移,因此保证合法。
放弃不讲。
然后就没啦?

// Code by ajcxsu
// Problem: keep the customer satisfied

#include<bits/stdc++.h>
using namespace std;

const int N=8e5+10;
struct Order {
    int t, e;
} o[N];
bool cmp(const Order &a, const Order &b) { return a.e<b.e; }

int main() {
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--) {
        int tot=0, n;
        cin>>n;
        for(int i=0;i<n;i++) cin>>o[i].t>>o[i].e;
        sort(o, o+n, cmp);
        priority_queue<int> pq;
        for(int i=0;i<n;i++) {
            if(tot+o[i].t>o[i].e) {
                if(pq.empty() || o[i].t>=pq.top()) continue;
                tot-=pq.top(), pq.pop(), pq.push(o[i].t), tot+=o[i].t;
            }
            else tot+=o[i].t, pq.push(o[i].t);
        }
        cout<<pq.size()<<endl;
        if(t) cout<<endl; // surprise mother fxxker
    }
    return 0;
}

本文链接:https://acxblog.site/archives/sol-uva-1153.html
本文采用 CC BY-NC-SA 3.0 协议进行许可