1155. 【贪心算法】智力大冲浪

题解

链接点我
题目：
1155. 【贪心算法】智力大冲浪 (Standard IO)
时间限制: 1000 ms 空间限制: 262144 KB 具体限制

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

输入
共4行：
第1行为m，表示一开始奖励给每位参赛者的钱；
第2行为n，表示有n个小游戏；
第3行有n个数，分别表示游戏1到n的规定完成期限；
第4行有n个数，分别表示游戏1到n不能在规定期限前完成的扣款数。

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

样例输入
10000
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10

样例输出
9950

#include<iostream>
using namespace std;
int a[1000],b[1000];
bool c[1000];
void q_sort(int i,int j)
{
    int mid,left,right;
    mid=b[rand()%(j-i)+i];
    left=i; right=j;
    while(i<=j)
    {
        while(b[i]<mid) i++;
        while(b[j]>mid) j--;
        if(i<=j)
        {
            a[0]=a[i];
            a[i]=a[j];
            a[j]=a[0];
            b[0]=b[i];
            b[i]=b[j];
            b[j]=b[0];
            i++; j--;
        }
    }
    if(left<j) q_sort(left,j);
    if(i<right) q_sort(i,right);
}
int main()
{
    int n,m;
    cin>>m>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        cin>>b[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n-1;j++)
        {
            if(b[j]<b[j+1])
            {
                int k=a[j];
                a[j]=a[j+1];
                a[j+1]=k;
                k=b[j];
                b[j]=b[j+1];
                b[j+1]=k;
            }
        }
    }
    int dp=0,pd=0,k=n;
    for(int i=1;i<=n;i++)
    {
        for(int j=a[i];j>=1;j--)
        {
            if(c[j]==0)
            {
                c[j]=1;
                break;
            }
            if(j==1)
            {
                m=m-b[i];
            }
        }
    }
    cout<<m;
}