傳送門
其實是個比較套路的貪心
按照結束時間排序,每個任務依次考慮過去
n o w now now代表當前做任務花費的時間
當我們要做第 i i i個任務的時候,首先讓 n o w + = x i now+=x_i now+=xi?
這時候,如果 n o w now now不大于結束時間,就往后考慮
如果 n o w now now比結束時間大了,說明前面的任務需要用金幣來騰出時間
用哪些任務來騰時間最劃算??當然是 z z z值比較小的那些任務
由于我們需要動態維護 [ 1 , i ] [1,i] [1,i]任務的 z z z值
所以搞一個優先佇列即可,每次把當前任務壓入佇列
動態維護之前每個任務還有多少時間可以用金幣換,看代碼就容易了，
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+10;
struct node{
int z,x,y;
bool operator < (const node&tmp ) const{ return z<tmp.z; }
}a[maxn]; int n;
bool com( node a,node b ){ return a.y<b.y; }
priority_queue<node>q;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&a[i].z,&a[i].x,&a[i].y );
sort( a+1,a+1+n,com );
int now = 0;//目前花費的時間
double ans = 0;//做完[1,i]任務需要花費的最少金幣
for(int i=1;i<=n;i++)
{
q.push( a[i] );
now += a[i].x;//加上完成時間
while( now>a[i].y )
{
node u = q.top(); q.pop();
int k = min( now-a[i].y,u.x );//用金幣購買的時間
ans += 1.0*k/u.z;
now -= k, u.x-=k;
if( u.x ) q.push( u );
}
}
printf("%.1f\n",ans);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/241428.html
標籤：其他
上一篇：簡陋的控制臺C語言五子棋
下一篇：2021JMU藍橋校選搜索bfs