Language:
Default
The lazy programmer
Description A new web-design studio, called SMART (Simply Masters of ART), employs two people. The first one is a web-designer and an executive director at the same time. The second one is a programmer. The director is so a nimble guy that the studio has already It is known that the programmer is lazy. Usually he does not work as fast as he could. Therefore, under normal conditions the programmer needs bi of time to perform the contract number i. Fortunately, the guy is very greedy for money. If The director has a difficult problem to solve. He needs to organize programmer’s job and, may be, assign extra payments for some of the contracts so that all contracts are performed in time. Obviously he wishes to minimize the sum of extra payments. Help Input The first line of the input contains the number of contracts N (1 ≤ N ≤ 100 000, integer). Each of the next N lines describes one contract and contains integer numbers ai, bi, di (1 Output The output needs to contain a single real number S in the only line of file. S is the minimum sum of money which the director needs to pay extra so that the programmer could perform all contracts in time. The number must Sample Input 2 Sample Output 5.00 Source
Northeastern Europe 2004, Western Subregion
|
/* 题意:有n个任务要完毕,每一个任务有属性 a,b,d
分别代表 额外工资,完毕时间,结束时间。
假设不给钱。那么完毕时间为b,给x的额外工资,那么完毕时间b变成 b-a*x 求在全部任务在各自最后期限前完毕所须要给的最少的钱 思路:先把任务依照结束之间排序,然后依次完毕每一个任务,假设这个任务无法完毕
那么在前面(包含这个)任务中找到a属性最大的任务(能够再给他钱的前提),
给钱这个腾出时间来完毕当前这个任务,而这个能够用优先队列维护 */ #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map> #define L(x) (x<<1)
#define R(x) (x<<1|1)
#define MID(x,y) ((x+y)>>1) #define eps 1e-8
typedef __int64 ll; #define fre(i,a,b) for(i = a; i <b; i++)
#define free(i,b,a) for(i = b; i >= a;i--)
#define mem(t, v) memset ((t) , v, sizeof(t))
#define ssf(n) scanf("%s", n)
#define sf(n) scanf("%d", &n)
#define sff(a,b) scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf printf
#define bug pf("Hi\n") using namespace std; #define INF 0x3f3f3f3f
#define N 100005 struct stud{
int a,b,d;
double money;
bool operator<(const stud b) const
{
return a<b.a;
} }f[N]; int cmp(stud x,stud y)
{
return x.d<y.d;
} priority_queue<stud>q; int n; int main()
{
int i,j;
while(~scanf("%d",&n))
{
for(i=0;i<n;i++)
{
scanf("%d%d%d",&f[i].a,&f[i].b,&f[i].d);
f[i].money=0; //已经给这个任务的钱
}
sort(f,f+n,cmp); while(!q.empty()) q.pop();
double ans,day;
ans=day=0;
stud cur;
for(i=0;i<n;i++)
{
q.push(f[i]);
day+=f[i].b;
while(day>f[i].d)
{
cur=q.top();
q.pop();
double temp=(double)(day-f[i].d)/cur.a; //完毕这个任务须要给cur任务的钱
if(temp+cur.money<(double)cur.b/cur.a) //假设这个钱加上已经给的钱小于能够给他的钱
{
day-=temp*cur.a;
cur.money+=temp;
ans+=temp;
q.push(cur);
break;
}
else
{
temp=((double)cur.b/cur.a-cur.money);
day-=temp*cur.a;
ans+=temp;
}
}
} printf("%.2f\n",ans);
}
return 0;
}
Language:
Default
The lazy programmer
Description A new web-design studio, called SMART (Simply Masters of ART), employs two people. The first one is a web-designer and an executive director at the same time. The second one is a programmer. The director is so a nimble guy that the studio has already It is known that the programmer is lazy. Usually he does not work as fast as he could. Therefore, under normal conditions the programmer needs bi of time to perform the contract number i. Fortunately, the guy is very greedy for money. If The director has a difficult problem to solve. He needs to organize programmer’s job and, may be, assign extra payments for some of the contracts so that all contracts are performed in time. Obviously he wishes to minimize the sum of extra payments. Help Input The first line of the input contains the number of contracts N (1 ≤ N ≤ 100 000, integer). Each of the next N lines describes one contract and contains integer numbers ai, bi, di (1 Output The output needs to contain a single real number S in the only line of file. S is the minimum sum of money which the director needs to pay extra so that the programmer could perform all contracts in time. The number must Sample Input 2 Sample Output 5.00 Source
Northeastern Europe 2004, Western Subregion
|