# 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;}`

## 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

## 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