题目描述

小伟报名参加电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。接下来主持人宣布了比赛规则：首先，比赛时间分为n个时段（n≤500），他又给出了很多小游戏，每个小游戏都必须在规定期限ti前完成，1≤ti≤n，如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣去一部分钱wi，wi为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，并保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！注意：比赛绝对不会让参赛者赔钱。

样例

in

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

out

9950

因为每个任务都用相同的时间，所以排序钱。

优先做扣得多的

如果该时段任务了，就一直往前推，直至有空为止，
如果没找到，就减去相应钱数。

贪心

#include <bits/stdc++.h>

using namespace std ;

const int N = 1e5 + 5 ;

struct shit {

    int t , m ; // 时间 ， 钱
    bool sht = false ; // 有没有位置

} ;

int k , n ;
shit a[N] ;
bool nshit[N] ;

bool cmp ( shit x , shit y ) {

    return x.m > y.m ;

}

int main ( ) {

    cin >> k >> n ;
    for ( int i = 1 ; i <= n ; i ++ ) cin >> a[i].t ;
    for ( int i = 1 ; i <= n ; i ++ ) cin >> a[i].m ;

    sort ( a + 1 , a + n + 1 , cmp ) ; // 排序

    for ( int i = 1 ; i <= n ; i ++ ) {

        if ( nshit[a[i].t] ) {

            for ( int j = a[i].t ; j >= 1 ; j -- ) 
                if ( !nshit[j] ) { 

                    nshit[j] = true ; 
                    a[i].sht = true ; 
                    break ; 

                } 
            // 枚举每一位至有空为止
        }        
        else {

            nshit[a[i].t] = true ;
            a[i].sht = true ;

        } 

    }

    for ( int i = 1 ; i <= n ; i ++ ) 
        if ( !a[i].sht ) k -= a[i].m ;

    cout << k ;    

    return 0 ;

}