学步园

POJ 2970

题意：

         有n个合同，每个合同的截止日期是di，有个程序员，他完成第i个合同的时间是bi，对于合同i如果给他x元钱，他完成第i个合同的时间就会变成bi-ai*x 。求需要的最少总钱数，使得存在一个方案使得程序员能按时完成所有合同。

分析：

        先按di排序，（从小到大）。然后依次完成合同，若发现第i个合同无法在截止日期前完成，便从之前已经完成的任务中选一个aj最大的合同，付钱来使得这个合同尽快完成。

 P.S:思路对了，但是下面的代码一直交不过。(T_T) (T_T)

code:

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <iostream>
#define MAXN 100005
using namespace std;
struct  contract {
    int a, b, d;
    bool operator < (const contract& t) const {
        return d<t.d;
    }
} f[MAXN];
struct pq {
    int a, b;
    bool operator < (const pq& t) const {
        return a <t.a;
    }
};
int main() {
    int n, i, j, Times, t;
    double ans;
    priority_queue<pq> q;
//    freopen("in.txt","r",stdin);
    scanf("%d",&n);
    for(i=0; i<n; i++)
        scanf("%d%d%d",&f[i].a,&f[i].b,&f[i].d);
    sort(f,f+n);
    Times =  0;
    ans = 0.0;
    for(i=0; i<n; i++) {
        Times += f[i].b;
        q.push(pq {f[i].a, f[i].b});
        while(Times >f[i].d) {
            t = Times - f[i].d;
            pq e = q.top();
            q.pop();
            if(e.b >=t) {
                e.b -=t;
                ans += double(t)/e.a;
                Times = f[i].d;
                q.push(e);
            } else {
                ans += double(e.b)/e.a;
                Times -= e.b;
                e.b = 0;
            }
        }
    }
    printf("%.2lf\n",ans);
    return 0;
}

AC

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cctype>
#include <climits>
#include <cmath>
#include <utility>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <map>
using namespace std;

#define pii pair < int , double >
#define i64 long long
#define CLR(x) memset(x,0,sizeof x)
#define SET(x,y) memset(x,y,sizeof x)
#define PB(x) push_back(x)
#define eps 1e-8

struct job{
	int a,b,d;
	void inp() {
		scanf("%d %d %d",&a,&b,&d);
	}
}d[100009];

bool comp(job a,job b) { return a.d<b.d; }

int main() {
	int n,i,T;
	double c,r;
	cin>>T;
	while(T--) {
		cin>>n;
		for(i=0;i<n;i++) d[i].inp();
		sort(d,d+n,comp);
		r=c=0;
		priority_queue < pii > q;
		pii t;
		for(i=0;i<n;i++) {
			c+=d[i].b;
			q.push(pii(d[i].a,d[i].b));
			while(c>d[i].d+eps) {
				t=q.top();
				q.pop();
				if(c-t.second>=d[i].d) {
					c-=t.second;
					r+=t.second/t.first;
				}
				else {
					t.second-=(c-d[i].d);
					r+=(c-d[i].d)/t.first;
					c=d[i].d;
					q.push(t);
				}
			}
		}
		printf("%.2lf\n",r);
	}
	return 0;
}