智力大冲浪

http://www.nowcoder.com/questionTerminal/8b9fe7ef0c9245c9a410ea2e8ce840c8

链接：https://ac.nowcoder.com/acm/contest/950/E
来源：牛客网

题目描述

小伟报名参加中央电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元。先不要太高兴！因为这些钱还不一定都是你的？！接下来主持人宣布了比赛规则：首先，比赛时间分为n个时段，它又给出了很多小游戏，每个小游戏都必须在规定期限ti前完成。如果一个游戏没能在规定期限前完成，则要从奖励费m元中扣去一部分钱wiw_iwi，wiw_iwi为自然数，不同的游戏扣去的钱是不一样的。当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序。作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱！注意：比赛绝对不会让参赛者赔钱！
输入描述:
输入共四行。第一行为m，表示一开始奖励给每位参赛者的钱；第二行为n，表示有n个小游戏；第三行有n个数，分别表示游戏1到n的规定完成期限；第四行有n个数，分别表示游戏1到n不能在规定期限前完成的扣款数。
输出描述:
输出仅一行，表示小伟能赢取最多的钱。

示例1
输入

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

9950

备注:
对于 100%100%100% 的数据，有n≤500,1≤ti≤nn \le 500 , 1 \le t_i \le nn≤500,1≤ti≤n

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

思路

我们直觉的思路就是设一个时间记录器。
但这是一个错误的贪心，按照样例来算答案会是9900
因为我们在保证花费降序时对时间要求完全是一个杂乱无章的处理。

可能值钱的任务时间限制也宽，有些即使不值钱的任务也容易超时，然而此时却完全可以避免那个即使便宜的任务的损耗。
我们考虑最优贪心，就是每一个任务都在最后一秒做，因为时间≤500\leq500≤500,可以设一个vis数组记录此时间是否被占用，当然，如果最后一秒被占用，就依次往前推，直到找到在越往后做，才能给其他时间紧的任务腾出时间，而又优先考虑大任务的完成，如果本任务已经没时间了就真的只能掏钱了。。。

废话少说，上代码

#include<bits/stdc++.h>
using namespace std;
struct ben{
    int t,val;
}a[505];
int vis[505];
int cmp(const ben &a,const ben &b){
    return a.val>b.val;
}
int main(){
    int m,n;
    cin>>m>>n;
    for(int i=1;i<=n;i++){
       cin>>a[i].t;
    } 
    for(int i=1;i<=n;i++){
        cin>>a[i].val;
    } 
    sort(a+1,a+n+1,cmp);
    int ans=0,t=0;
    for(int i=1;i<=n;i++){
        int tag=0;
        for(int j=a[i].t;j;j--){
            if(vis[j]==0){
                vis[j]=1;
                tag=1;
                break;
            }
        }
        if(tag==0){
            for(int j=n;j;j--){
                if(vis[j]==0){
                    vis[j]=1;
                    break;
                }
            }
            ans+=a[i].val;
        }
    }
   cout<<m-ans; 
    return 0;
}

然后，你就可以AC啦！
图片说明