威尼斯人娱乐各样小游戏都必须在规定限时ti前实现(一≤ti≤n),主持人只是想考考每一种参加比赛者怎么着安顿组织协和做游戏的依次

难点叙述

小伟报名出席中央电视台的智力商数大冲浪节目。此次挑衅赛吸引了大多参赛者,主持人为了赞赏咱们的胆子,先表彰每一种参赛者m元。先不用太开心!因为那几个钱还不肯定都是你的?!接下去主持人发布了比赛规则:

第3,竞技时间分为n个时段(n≤500),它又提交了众多小游戏,每一种小游戏都无法不在规定时期限制ti前产生(壹≤ti≤n)。假如2个娱乐没能在规定时限前产生,则要从奖赏费m元中扣去壹部分钱wi,wi为自然数,不一样的游玩扣去的钱是不等同的。当然,每种游戏自个儿都很简短,保障每一个参加比赛者都能在贰个时段内做到,而且都必须从整时段开头。主持人只是想考考各样参加比赛者怎样布署组织和煦做游戏的相继。作为参加比赛者,小伟很想赢得季军,当然更想赢取最多的钱!注意:比赛相对不会让参加比赛者赔钱!

 智力大冲浪(riddl)

输入输出格式

输入格式:

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

第贰行为m,表示一同先嘉勉给各位参加比赛者的钱;

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

第一行有n个数,分别表示游戏一到n的分明完毕限制期限;

第伍行有n个数,分别代表游戏1到n不可能在规定时限前实现的扣款数。

输出格式:

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

问题

小伟报名参预中央广播台的灵气大冲浪节目。本次挑衅赛吸引了累累参加比赛者,主持人为了表扬我们的勇气,先奖赏各类参加比赛者m元。先不用太心情舒畅!因为那一个钱还不明确都以您的?!接下去主持人发表了竞赛规则:

先,比赛时间分为n个时段(n≤500),它又交给了繁多小游戏,每种小游戏都必须在明确年限ti
前成功(一≤ti≤n)。要是一个嬉戏没能在显著有效期前实现,则要从嘉勉费m元中扣去壹部分钱wi,wi为自然数,区别的游乐扣去的钱是分化的。当然,
种种游戏自个儿都很粗大略,保障每个参加比赛者都能再二个时光内做到,而且都必须从整时段初步。主持人只是想考考每一个参加比赛者怎么样布署组织团结做游戏的依次。作为参赛者,小伟很想获取季军,当然更想赢取最多的钱!注意:竞赛相对不会让参加比赛者赔钱。

输入输出样例

输入样例#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;
}

 

 

 

   
桂冠上的飘带,不是用天才纤维捻制而成的,而是用痛心,横祸的丝缕纺织出来的。

输入

共4行:
第一行为m,表示一同来表彰给每位参加比赛者的钱;
第三行为n,表示有n个小游戏;
第三行有n个数,分别表示游戏1到n的鲜明落成期限;
第5行有n个数,分别代表游戏壹到n不可能在规定年限前成功的扣款数。

输出

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

样例输入

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

样例输出

9950

解析

我们可以按金钱的多少排序,我们可以把游戏在规定期限的顺序,并用数组记录,如果该规定期限有游戏存在,我们可以把它放在前面一个空着的(直到1~t内全部占满)。

威尼斯人娱乐 1威尼斯人娱乐 2

#include <bits/stdc++.h>

using namespace std;
const int maxn = 502;
struct times {
    int a, b;

};
bool cmp(times a, times b) {
    if(a.b == b.b) {
        return a.a < b.a;
    }
    return a.b > b.b;
}


int main() {
    int  n, sum, a[maxn];
    times s[maxn];
    scanf("%d%d", &sum, &n);
    for(int i = 0; i < n; i++) {
        a[i] = -1;
        scanf("%d", &s[i].a);
        s[i].a -= 1;
    }
    for(int i = 0; i < n; i++) {
        scanf("%d", &s[i].b);
    }
    sort(s, s+n, cmp);

    int sum1 = 0;
    for(int i = 0; i < n; i++) {
                int m = s[i].a;

                while(m >= 0) {
                    if(a[m] == -1) {
                        a[m] = i;
                        break;
                    } else if(m > 0) {
                        m--;
                    } else if(m == 0) {

                        sum1 += s[i].b;
                        break;
                    }
                }


    }
    printf("%d\n",sum - sum1);

}

View Code