P1230 智力大冲浪

题目描述

小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者 $m$ 元。先不要太高兴，因为这些钱还不一定都是你的。接下来主持人宣布了比赛规则：

首先，比赛时间分为 $n$ 个时段，它又给出了很多小游戏，每个小游戏都必须在规定期限 $t_i$ 前完成。如果一个游戏没能在规定期限前完成，则要从奖励费 $m$ 元中扣去一部分钱 $w_i$，$w_i$ 为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！注意：比赛绝对不会让参赛者赔钱!

输入格式

第一行为 $m$，表示一开始奖励给每位参赛者的钱；

第二行为 $n$，表示有 $n$ 个小游戏；

第三行有 $n$ 个数，分别表示游戏 $1$ 到 $n$ 的规定完成期限；

第四行有 $n$ 个数，分别表示游戏 $1$ 到 $n$ 不能在规定期限前完成的扣款数。

输出格式

输出仅一行，表示小伟能赢取最多的钱。

输入输出样例 #1

输入 #1

10000
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10

输出 #1

9950

说明/提示

对于 $100\%$ 的数据，$1\le n\le 500$，$1\le m\le 5\times 10^5$，$1\le t_i\le n$，$1\le w_i\le 1000$。

C++实现

#include
#include
using namespace std;
int hash[5000001];
struct ben{
int x,y;
}a[501];
int cmp(const ben &a,const ben &b){
return a.y>b.y;
}
int main(){
int m,n;
scanf(“%d%d”,&m,&n);
for(int i=1;i<=n;i++)scanf(“%d”,&a[i].x);//完成期限
for(int i=1;i<=n;i++)scanf(“%d”,&a[i].y);//罚款
sort(a+1,a+n+1,cmp);//按照罚款数额从大到小进行选择排序
int bj=0;
int s=0;
for(int i=1;i<=n;i++){
bj=1;
for(int j=a[i].x;j>=1;j–){
if(hash[j]0){
bj=0;
hash[j]=1;
break;
}
}
if(bj1){
for(int k=n;k>=1;k–){
if(hash[k]==0){
hash[k]=1;
break;
}
}
s+=a[i].y;//累加罚款
}
}
printf(“%d”,m-s);
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容