LUOGU P2949 [USACO09OPEN]工作调度Work Scheduling (贪心)
2024-08-29 11:20:43
解题思路
明明一道比较简单的贪心结果挂了好几次23333,就是按照时间排序,然后拿一个小根堆维护放进去的,如果时间允许就入队并且记录答案。如果不允许就从堆里拿一个最小的比较。
#include<bits/stdc++.h> using namespace std;
const int MAXN = ; inline int rd(){
int x=,f=;char ch=getchar();
while(!isdigit(ch)) {f=ch=='-'?:;ch=getchar();}
while(isdigit(ch)) {x=(x<<)+(x<<)+ch-'';ch=getchar();}
return f?x:-x;
} int n,res;
long long ans; struct Data{
int p,t;
}data[MAXN]; priority_queue<int,vector<int>,greater<int> > Q; inline bool cmp(Data A,Data B){
return A.t==B.t?A.p>B.p:A.t<B.t;
} int main(){
n=rd();
for(int i=;i<=n;i++) data[i].t=rd(),data[i].p=rd();
sort(data+,data++n,cmp);
for(int i=;i<=n;i++){
if(res<data[i].t) ans+=data[i].p,res++,Q.push(data[i].p);
else {
int x=Q.top();
if(data[i].p>x) ans+=data[i].p-x,Q.pop(),Q.push(data[i].p);
}
}
cout<<ans;
return ;
}
最新文章
- java占位符应用
- Day6-python基础之模块
- ESP8266刷AT固件与nodemcu固件
- JNI输出log信息
- 【linux】ubuntu stmp服务器配置
- 图解Android - Binder 和 Service
- 在 Node.js 上调用 WCF Web 服务
- 用命令 安装/卸载 windows服务(转)
- UVALive 2517	Moving Object Recognition(模拟)
- 芝麻HTTP: Python爬虫入门之Urllib库的高级用法
- Windows10 64位系统安装 .NET Framework 3.5
- [Ubuntu]pkg-config和ldconfig
- THUWC2018游记
- 谈谈canvas的性能优化(主要讲缓存问题)
- 20175314 《Java程序设计》第三周学习总结
- 第一次参加acm区域赛
- 实现了一下Mp3播放器的功能
- 织梦 百度sitemap制作教程
- c# 文字首字母
- 术语-服务:BaaS