UVA 1153 KEEP THE CUSTOMER SATISFIED

题意:

  钢铁公司有N个客户的订单,每个订单有一个产量q(生产时间刚好也等于q)和订单完成截止时间。公司要求完成尽量多的订单。

分析:

  先按截止时间d排序,然后维护一个已经选好的订单的优先队列,如果当前无法选择的话,那么尝试和之前花费时间最长的交换。如果qi<qj的话,交换之后花费的时间更短且截止时间di更长。

代码:

  

#include<iostream>#include<cstdio>#include<algorithm>#include<queue>using namespace std;const int MAXN=800005;struct NODE{    int q;    int d;};NODE a[MAXN];int n;bool cmp(NODE a,NODE b){    return a.d<b.d;}int main(){    int i,ans;    int T;    scanf("%d",&T);    while(T--)    {        scanf("%d",&n);        for(i=0; i<n; i++)            scanf("%d%d",&a[i].q,&a[i].d);        sort(a,a+n,cmp);        priority_queue<int>q;        while(!q.empty())             q.pop();        ans=0;        for(i=0;i<n;i++)        {            if(a[i].q+ans>a[i].d)            {                if(!q.empty())                {                    if((q.top()>a[i].q)&&((ans+a[i].q-q.top())<=a[i].d))                    {                        ans-=q.top();                        q.pop();                        q.push(a[i].q);                        ans+=a[i].q;                    }                }            }            else            {                q.push(a[i].q);                ans+=a[i].q;            }        }        printf("%d\n",q.size());        if(T)             printf("\n");    }    return 0;}
时间: 11-01

UVA 1153 KEEP THE CUSTOMER SATISFIED的相关文章

UVA - 1153 Keep the Customer Satisfied(贪心)

UVA - 1153 Keep the Customer Satisfied Time Limit: 3000MS   Memory Limit: Unknown   64bit IO Format: %lld & %llu Description Simon and Garfunkel Corporation (SG Corp.) is a large steel-making company with thousand of customers. Keeping the customer s

UVA 1153 Keep the Customer Satisfied 顾客是上帝(贪心)

因为每增加一个订单,时间是会增加的,所以先按截止时间d排序,这样的话无论是删除一个订单,或者增加订单,都不会影响已经选好的订单.然后维护一个已经选好的订单的大根堆(优先队列),如果当前无法选择的话,那么尝试和之前花费时间最长的交换.如果qi<qj的话,交换之后花费的时间更短且截止时间di更长,情况不会比没交换更糟·. #include<bits/stdc++.h> using namespace std; const int maxn = 8e5+5; struct Cus { int

Uva 1153 Keep the Customer Satisfied (贪心+优先队列)

题意:已知有n个工作,已知每个工作需要的工作时间qi和截至时间di,工作只能串行完成,问最多能完成多少个工作 思路:首先我们按照截至时间从小到大排序,让它们依次进入优先队列中,当发生执行完成时间大于截至时间时,我通过优先队列把工作中最长的需要时间出队 优先队列的比较函数: struct cp { bool operator () (node a,node b) { //可以理解为我如何让后入队的优先出队 if(b.need>a.need) return true; else return fal

UVa 1153 Keep the Customer Satisfied (贪心+优先队列)

题意:给定 n 个工作,已知每个工作要用的时间 q 和 截止时间 d,问你最多完成多少个工作,每次最多能运行一个工作. 析:这个题是贪心,应该能看出来,关键是贪心策略是什么,这样想,先按截止时间排序,那么这样,所有的工作就是都是按照截止时间排,因为我们先保证, 截止时间早的先选,然后再从把所有的遍历一下,利用优先队列,q大的优先,然后考虑,后面的,如果后面的还能在截止时间内完成,就放入,如果不能,那么, 和队列中q最长的比,如果比队列中q最长的还长,那么就不要了,否则,那么就删除最长的,把它放进

1153 - Keep the Customer Satisfied(贪心)

又是一道经典的贪心算法题目 . 乍看题目,想到了紫书一开始讲的区间问题(给定一些区间,选择尽可能多的不相交区间),和另一个经典问题:"活动安排"  的实质是一样的. 但是本题又和区间问题不同,因为区间起点未知,我们所知道的仅仅是等待时间和截至时间,但是其实贪心思想是一致的,即:尽可能的给后面的人留下更多时间,满足当前所用时间最少. 因此可以写出贪心算法 : 按照截至时间排序,将元素的消耗时间加到优先队列里,这样队首元素就是消耗时间最长的人,如果加上当前的人时间超过了他的截至时间,那么将

poj 2786 - Keep the Customer Satisfied

Description Simon and Garfunkel Corporation (SG Corp.) is a large steel-making company with thousand of customers. Keeping the customer satisfied is one of the major objective of Paul and Art, the managers. Customers issue orders that are characteriz

UVA1153-Keep the Customer Satisfied(贪心)

Problem UVA1153-Keep the Customer Satisfied Accept: 222  Submit: 1706Time Limit: 3000 mSec Problem Description Input The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as des

UVA-1153 Keep the Customer Satisfied (贪心)

题目大意:有n件工作,做每件工作的消耗时间为s,截止时间为d,问最多能做完几件工作. 题目分析:贪心策略:优先做截止时间靠前的,一旦做不完当前工作,则从已经做过的工作中删去一件耗时最长的,用当前工作取代之. 代码如下: # include<iostream> # include<cstdio> # include<vector> # include<queue> # include<cstring> # include<algorithm&

Keep the Customer Satisfied

题意: n个订单,每个订单有完成需要的天数,和限制的天数,求最多能完成多少订单 分析: 先按限制日期升序排列,若当前订单不能完成,和上面已选中的订单中需要天数中最大的比较,若比它小,则替换他. #include <map> #include <set> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #