一、題目大意
小偉報名參加中央電視臺的智力大沖浪節目，本次挑戰賽吸引了眾多參賽者，主持人為了表彰大家的勇氣，先獎勵每個參賽者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行，表示小偉能贏取最多的錢
【sample input】
? 10000
? 7
? 4?? 2??? 4?? 3?? 1?? 4?? 6
? 70 ?60?? 50 ?40 ?30 ?20 ?10
【sample output】
? 9950
二、大致思路
? ? ? ? 這道題數據有很多，但是要學會排除掉多余干擾因素。因為要讓剩余的獎金最大化，所以我們可以按照未完成游戲時所扣金額的大小排序（這里我按照從大到小進行排序），首先選擇進行扣錢金額大的游戲。那么問題來了，每個游戲都有固定的截止時間，有很多扣錢大的游戲相互沖突，怎么辦？相信很多人都會卡在這個問題上。我們可以通過以下方法實現所得獎金最大化：我們按上述方法排序后，從左到右遍歷，能在對應時間段完成的，就完成；不能在該時間段完成的，就找一個在該游戲截止時間之前的時間段完成游戲，如果找不到，則放棄。
? ? ? ? 下面以一個具體的例子進行遍歷：
? ? ? ? 游戲截止時間：?4? ? 2? ? ?4? ? 3? ? 1? ? 4? ? 6
? ? ? ? 游行名稱：? ? ? ? A? ? B? ? C? ? D? ?E? ? F? ?G
? ? ? ? ?所扣金額：? ? ? 70 ?60?? 50 ?40 ?30 ?20 ?10
? ?為了方便起見，我在這里就統一用時刻代表何時完成游戲（時刻和時間段不一樣）。如上表所示，從左到右對游戲進行遍歷，我們在4s進行A游戲，2S進行B游戲，下一個游戲本來要在4s進行，但是4S已經被占用了，所以要向下（游戲截止前）找一個空余時間去完成該游戲，在對時間向下遍歷的時候發現3S沒被占用，所以用3S進行C游戲。繼續遍歷，遇到D游戲，但是3S已經被占用，同理對時間向下遍歷：2S不行，1S可以，所以用1S進行D游戲。繼續對游戲向右遍歷，遇到E游戲，本來在1S進行，但是被占用了，然后對時間向下遍歷，在1S前沒有空時間，所以就放棄E游戲。對游戲繼續遍歷，同理F游戲也得放棄，最后的G游戲可以進行。整個遍歷的過程就是這樣，復雜度N方。
三、具體實現
? ? ? ? 我用C語言寫的代碼，在代碼開頭，定義一個數組，并初始化為0，用來對各個時間是否被使用進行標記，1為使用。然后定義一個game結構體，并設置f（finish代表游戲截止時間），d（decrease代表罰金），p（position代表有一是否進行1表示進行，0代表未進行）三個屬性。之后就是照著之前的分析進行代碼設計。
#include<stdlib.h>
#include<algorithm>
#include<stdio.h>
#include<iostream>
using namespace std;
int m;//代表開始獎勵給每位參賽者的錢
int b[6000] = { 0 };//記錄時間段是否被使用，使用標記為1
//定義一個游戲結構體，存儲游戲的屬性
struct game
{int f;//表示游戲1到n的規定完成期限int d;//表示游戲1到n不能在規定期限前完成的扣款數int p = 0;//1表示對應的游戲已完成，0表示未完成
};
//用bool函數對排序依據的因素進行選擇
bool cmp(game f, game d)
{return f.d > d.d;//選擇罰款項進行非增序排序
}
//此函數為計算最小扣款函數
int compu(int n, game a[])
{sort(a, a + n, cmp);//對罰款進行非遞增排序int i, j;//循環變量//外層循環對已排好序的游戲，進行從左到右的遍歷for (i = 0; i<n; i++){//如果游戲對應的時間段沒有被占用，則進行該游戲if (b[a[i].f] == 0){a[i].p = 1;//對游戲中是否完成的屬性進行修改，表明該游戲已完成b[a[i].f] = 1;//對游戲使用的時間段進行標記continue;//進行下一個游戲的判斷}//游戲對應的時間段已被占用else{for (j = (a[i].f - 1); j >0; j--){//表明找到空閑時間段完成本游戲if (b[j] == 0){a[i].p = 1;//對游戲中是否完成的屬性進行修改，表明該游戲已完成b[j] = 1;//對游戲使用的時間段進行標記break;}//表明未找到空閑時間段完成本游戲,繼續循環找elsecontinue;}}}return m;
}
int main()
{game a[6000];//定義游戲int n;//表示有n個小游戲cout << "請輸入開始時獎勵給每位參賽者的錢款金額：" << endl;cin >> m;cout << "請輸入小游戲的個數：" << endl;cin >> n;int i = 0;//循環變量cout << "請輸入每個游戲規定完成的期限：" << endl;for (i = 0; i <n; i++){cin >> a[i].f;}cout << "請輸入每個游戲不能在規定期限前完成的扣款數：" << endl;for (i = 0; i < n; i++){cin >> a[i].d;}int sum = 0;//表示小偉的獲獎金額sum = compu(n, a);for (i = 0; i < n; i++){if (a[i].p == 0)sum = sum - a[i].d;}if (sum < 0)sum = 0;cout << "小偉最多得獎的金額數為：" << sum << endl;system("pause");return 0;
}
)