acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 资讯
  • 竞赛
  • 讨论
  • 团队
  • 商城
登录
注册
题目详情提交记录(0)
  • 优先队列+贪心

    逆序,看那个可选的游戏分值最高,该时间段选哪个,优先队列维护当前最优选择,所有最优时间段就是整体最优,以下为代码:

    userId_undefined
    清风明月
    时间刺客空间掌握者时空双修者秩序白银
    164阅读
    0回复
    6点赞
  • 题解

    用结构体存一下ti和ri, 用个bool的数组存该时间段是否被占 参考代码:

    userId_undefined
    131****5886
    空间掌握者I/O·IO入门者俄罗斯套娃大师倔强青铜格式·格式排版员循环·循环打卡人
    52阅读
    1回复
    3点赞
  • 反悔贪心

    先按时间从小到大排序,再怎么排序都可以。因为优先队列会维护当前选择最优 代码如下: #include<bits/stdc++.h> using namespace std; struct s{ int w,t; }a[1000]; bool cmp(s x,s y){ if(x.t!=y.t)return x.t<y.t; return x.w<y.w; } signed main(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i].t; } for(int i=1;i<=n;i++){ cin>>a[i].w; } sort(a+1,a+n+1,cmp); priority_queue<int,vector<int>,greater<int>>pq; int ans=0; for(int i=1;i<=n;i++){ //cout << a[i].t<<" "<<a[i].w<<endl; if(pq.size()<a[i].t){ pq.push(a[i].w); ans+=a[i].w; } else{ if(a[i].w>pq.top()){ ans-=pq.top(); pq.pop(); pq.push(a[i].w); ans+=a[i].w; } } } cout << ans; return 0; }

    userId_undefined
    159****9233
    时间刺客空间掌握者倔强青铜递归·套娃学徒造物者模拟·模拟练习生
    4阅读
    0回复
    0点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页