担保每一种参加比赛者都能在三个时段内达成,保证种种参加比赛者都能在叁个时节内成功

3007 智力大冲浪

 

时限: 1 s

空间限制: 127000 KB

标题等第 : 白银 Gold

 

主题素材陈诉 Description

小伟报名参加中央电视台的灵气大冲浪节目。此次挑战赛迷惑了繁多参加比赛者,主持人为了赞叹大家的胆子,先嘉勉每一种参加比赛者m元。先不要太欢跃!因为那么些钱还不鲜明都是你的。接下来主持人发布了竞赛准则:
首先,比赛时间分为n个时段(n≤500),它又提交了好些个小游戏,每一个小游戏都不可能不在鲜明年限ti前完毕(1≤ti≤n)。假设一个嬉戏未能在显明限制期限前成功,则要从奖赏费m元中扣去一部分钱wi,wi为自然数,差异的游艺扣去的钱是不一样的。当然,每一种游戏本身都很简短,保障各类参赛者都能在一个时段内成功,並且都不可能不从整时段早先。主持人只是想考考每一种参加比赛者怎么着陈设协会团结做游戏的逐一。作为参加比赛者,小伟很想获取季军,当然更想赢取最多的钱!
注意:比赛相对不会让参赛者赔钱!

输入描述 Input Description

输入共4行。

先是行为m,表示一齐头嘉勉给每鬼盖赛者的钱;

其次行为n,表示有n个小游戏;
第三行有n个数,分别表示游戏1~n的规定完成限制期限;

第四行有n个数,分别表示游戏1~n不能在规定限制期限前产生的扣款数。

出口描述 Output Description

仅1行。表示小伟能赢取最多的钱。

样例输入 Sample Input

10000

7

4 2 4 3 1 4 6

70 60 50 40 30 20 10

样例输出 Sample Output

9950

数据范围及提醒 Data Size & Hint

n≤500

1≤ti≤n

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 int a[510],t[510],money[510];
 5 int m,n,k,l,s=0;
 6 int main()
 7 {
 8     scanf("%d%d",&m,&n);
 9     for(int i=1; i<=n; i++)
10     {
11         scanf("%d",&t[i]);  //时间 
12     }
13     for(int i=1; i<=n; i++)
14     {
15         scanf("%d",&money[i]);  //扣除的钱 
16         m-=money[i];     //假设游戏时 做完一个得到一个游戏的钱,不是扣除 
17     }
18     for(int i=1; i<=n-1; i++)  //按扣除钱的多少排序 
19         for(int j=i+1; j<=n; j++)
20             if(money[i]<money[j])
21             {
22                 swap(money[i],money[j]);
23                 swap(t[i],t[j]);
24             }
25     for (int i=1;i<=n;i++)  //a[j]表示做完第j个游戏,获得的金钱 
26         for (int j=t[i];j>=1;j--)
27             if(a[j]==0)
28             {
29                 a[j]=money[i];
30                 break;
31             }
32     for (int i=1;i<=n;i++)
33         s+=a[i];
34     printf("%d",m+s);
35 }

 

难题汇报

小伟报名参与中央电台的智力大冲浪节目。此番挑衅赛吸引了大多参加比赛者,主持人为了表扬大家的胆气,先嘉勉每一种参加比赛者m元。先不用太开心!因为这几个钱还不必然都是你的?!接下去主持人发布了比赛准绳:

第一,竞赛时间分为n个时段(n≤500),它又交给了过多小游戏,每一个小游戏都必须在规定有效期ti前成功(1≤ti≤n)。假如一个玩耍未能在规定时期限制前产生,则要从表彰费m元中扣去一部分钱wi,wi为自然数,分歧的游戏扣去的钱是分化样的。当然,每种游戏自身都相当粗略,保障各类参加比赛者都能在三个时节内到位,何况都必须从整时段发轫。主持人只是想考考每一个参加比赛者怎么样陈设组织本人做游戏的逐个。作为参加比赛者,小伟很想获得季军,当然更想赢取最多的钱!注意:竞赛相对不会让参加比赛者赔钱!

输入输出格式

输入格式:

输入文件riddle.in,共4行。

第1行为m,表示一方始嘉奖给各位参加比赛者的钱;

第2行为n,表示有n个小游戏;

第3行有n个数,分别代表游戏1到n的规定完结期限;

第4行有n个数,分别代表游戏1到n不可能在规按期限前产生的扣款数。

输出格式:

输出文件riddle.out,仅1行。表示小伟能赢取最多的钱。

输入输出样例

输入样例#1:

10000

7

4 2 4 3 1 4 6

70 60 50 40 30 20 10

输出样例#1:

9950

代码

#include <cstdio>
#include <algorithm>
#define Size 510
using namespace std;
typedef struct _Every{
    int t,w;
}Every;
Every e[Size];
int flag[Size] = {0};
int cmp(Every a,Every b){
    return a.w > b.w;
}
int main(){
    int p,n;
    scanf("%d %d",&p,&n);
    for(int i = 0; i < n; i++) scanf("%d",&e[i].t);
    for(int i = 0; i < n; i++) scanf("%d",&e[i].w);
    sort(e,e+n,cmp);         //快排
    for(int i = 0; i < n; i++)
    {
        int h = -1;               //h  标记位
        for(int j = e[i].t; j >= 1; j--) //注意,必须是倒序!!!
          if(!flag[j])
          { 
          h = j; 
          break;
           }        
        if(h != -1) flag[h] = 1;
        else p -= e[i].w;
    }
    printf("%d\n",p);
    return 0;
}

 

 

 

   
桂冠上的飘带,不是用天才纤维捻制而成的,而是用难受,悲惨的丝缕纺织出来的。

相关文章