【P1230 智力大冲浪】题解
2021/12/4 23:19:42
本文主要是介绍【P1230 智力大冲浪】题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接
题目
小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者,主持人为了表彰大家的勇气,先奖励每个参赛者m元。先不要太高兴!因为这些钱还不一定都是你的?!接下来主持人宣布了比赛规则:
首先,比赛时间分为n个时段(n≤500),它又给出了很多小游戏,每个小游戏都必须在规定期限ti前完成(1≤ti≤n)。如果一个游戏没能在规定期限前完成,则要从奖励费m元中扣去一部分钱wi,wi为自然数,不同的游戏扣去的钱是不一样的。当然,每个游戏本身都很简单,保证每个参赛者都能在一个时段内完成,而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者,小伟很想赢得冠军,当然更想赢取最多的钱!注意:比赛绝对不会让参赛者赔钱!
思路
按价钱从大到小排序。每个游戏尽量完成,且完成时间尽量后。
这样可以留多点时间给前面的。
而且先处理价格大的可以保证答案正确。
Code
// Problem: P1230 智力大冲浪 // Contest: Luogu // URL: https://www.luogu.com.cn/problem/P1230 // Memory Limit: 125 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) #include<bits/stdc++.h> using namespace std; //#define int long long inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+ (x<<3)+(ch^48);ch=getchar();}return x*f;} //#define M //#define mo //#define N struct node { int t, v; }a[510]; int n, m, i, j, k; int b[10000010]; bool cmp(node x, node y) { return x.v>y.v; } signed main() { // freopen("tiaoshi.in", "r", stdin); // freopen("tiaoshi.out", "w", stdout); m=read(); n=read(); for(i=1; i<=n; ++i) a[i].t=read(); for(i=1; i<=n; ++i) a[i].v=read(); sort(a+1, a+n+1, cmp); for(i=1; i<=n; ++i) { while(b[a[i].t]&&a[i].t) --a[i].t; if(a[i].t) b[a[i].t]=1; else k+=a[i].v; } printf("%d", max(0, m-k)); return 0; }
这篇关于【P1230 智力大冲浪】题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求