題目鏈接:https://vjudge.net/problem/UVA-207
題目描述:(簡單描述)
一場高爾夫比賽,分四輪由驹,每個選手都打完前兩輪蔓榄,前70名(包括并列)晉級甥郑,再打兩輪荤西,最后四輪總分前70名(包括并列)都有獎金。成績是越少越好勉躺。
要求:給出總獎金和每個名次獲獎比例(前70名)饵溅,還有所有選手的名字和每輪成績
輸出所有晉級到后兩輪的選手的信息概说,從第一名開始嚣伐,并列選手按名字字典做升序輸出轩端,輸出選手的名字基茵,排名,各輪得分弥臼,總分径缅,獎金數(shù)烙肺。
注意:
1桃笙、選手分為職業(yè)和業(yè)余搏明,業(yè)余名字結尾帶*,可晉級脚祟,參與排名由桌,但最后沒有獎金行您。
?????若業(yè)余選手得到了第三名,則第四名(非業(yè)余)拿第三名的獎金比例炕檩,以此類推
2笛质、選手每輪都有可能犯規(guī)妇押,即該輪成績處記為DQ敲霍,則后面輪次沒有成績丁存。
? ? ?若為晉級選手解寝,輸出時排在最后聋伦,沒有名次,總分記為DQ索守。
? ? ?若有犯規(guī)選手并列卵佛,則先按輪數(shù)排序截汪,然后按各輪得分之和排序植捎,最后按名字排序
3焰枢、最后如果第k名有n名選手并列,則k~k+n-1名的獎金比例相加后平均分給這n人暑椰。
? ? ?輸出時并列選手名次后加一個標記T一汽。
4、獎金四舍五入到美分岩喷。如果沒取消資格(沒犯規(guī))的非業(yè)余選手小于70名纱意,剩下的獎金就不發(fā)了妇穴。
? ? ? 只要選手在前70名隶债,獎金為0也要輸出死讹。
5赞警、輸入時愧旦,只要選手沒犯規(guī),就會給出四輪成績
? ?(就算沒晉級也會有定罢,但在實際比賽中沒晉級的選手應該只有兩個成績)
整體分析:
? ? 第一步是選出晉級選手祖凫,先對前兩輪得分進行排序惠况。接下來計算4輪總分,然后再排序一次峦睡,最后對排序結果依次輸出。
題目輸入格式:(原題是英文拉队,這里是用谷歌翻譯,有些地方會有出入阻逮,看得懂英文的建議點上面鏈接)
題目輸出格式:(同上)
大致流程圖:
代碼:(這是GitHub上的紫書代碼,加我的一些注釋)
(用vs2019編譯器瓜富,原碼中的gets(s)不讓編譯与柑,所以我都換成了cin.getline(s,40),不影響結果)
原碼鏈接:https://github.com/aoapc-book/aoapc-bac2nd/blob/master/ch5/UVa207.cpp
//UVa207 PGA Tour Prize Money
//Rujia Liu
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cassert>?
using namespace std;
#define REP(i,n) for(int i = 0; i < (n); i++)
const int maxn = 144;
const int n_cut = 70;
struct Player {
char name[25];
int amateur; //標記是否為業(yè)余選手
int sc[4]; //記錄每個成績
int sc36, //記錄前兩輪總分
sc72, //記錄總分
dq; //標記是否犯規(guī)
int rnds; //若犯規(guī)丑念,記錄已完成的場次
} player[maxn];
int n;
double purse, p[n_cut];
bool cmp1(const Player& p1, const Player& p2) {
if (p1.sc36 < 0 && p2.sc36 < 0) return false; // equal sc36<0說明為犯規(guī)選手脯倚,無法晉級推正,排最后
if (p1.sc36 < 0) return false; // p2 smaller
if (p2.sc36 < 0) return true; // p1 smaller
return p1.sc36 < p2.sc36;
}
bool cmp2(const Player& p1, const Player& p2) {
if (p1.dq && p2.dq) { /*如果都是DQ選手植榕,場次多的->總分小的->名字字典小的*/
if (p1.rnds != p2.rnds) return p2.rnds < p1.rnds;
if (p1.sc72 != p2.sc72) return p1.sc72 < p2.sc72;
return strcmp(p1.name, p2.name) < 0;
}
if (p1.dq) return false; //是否QD選手->總分小的->名字字典小的
if (p2.dq) return true;
if (p1.sc72 != p2.sc72) return p1.sc72 < p2.sc72;
return strcmp(p1.name, p2.name) < 0;
}
void print_result() {
printf("Player Name? ? ? ? ? Place? ? RD1? RD2");
printf("? RD3? RD4? TOTAL? ? Money Won\n");
printf("---------------------------------------");
printf("--------------------------------\n");
int i = 0, pos = 0;
while (i < n) {
if (player[i].dq) //如果為DQ選手尊残,只輸出已完成的成績汞斧,未完成的輸出空格粘勒,總分記為DQ
{
printf("%s? ? ? ? ? ", player[i].name);
REP(j, player[i].rnds) printf("%-5d", player[i].sc[j]);
REP(j, 4 - player[i].rnds) printf("? ? ");
printf("DQ\n");
i++;
continue;
}
int j = i;
int m = 0; // number of tied players 并列人數(shù)(可以分獎金的庙睡,業(yè)余不算)
bool have_money = false;
double tot = 0.0; // total pooled money
while (j < n && player[i].sc72 == player[j].sc72) { /*1技俐、檢測選手本身是否為業(yè)余選手
2雕擂、檢測是否有并列井赌,并列選手是否為業(yè)余選手*/
if (!player[j].amateur) {
m++;
if (pos < n_cut) {
have_money = true; // yeah! they still have money
tot += p[pos++];
}
}
j++;
}
// print player [i,j) together because they have the same rank
int rank = i + 1; // rank of all these m players 名次(因為i從0開始仇穗,要加1)
double amount = purse * tot / m; // if m=0, amount will be nan but we don't use it in that case :)
while (i < j) {
printf("%s ", player[i].name);
char t[5];
sprintf(t, "%d%c", rank, m > 1 && have_money && !player[i].amateur ? 'T' : ' '); //輸出名次纹坐,同時檢測是否有并列耘子,有就加T
printf("%-10s", t);
REP(e, 4) printf("%-5d", player[i].sc[e]);
// with prize
if (!player[i].amateur && have_money) { //檢測是否可以有獎金球切。(不是業(yè)余)
printf("%-10d", player[i].sc72);
printf("$%9.2lf\n", amount / 100.0);
}
else
printf("%d\n", player[i].sc72);
i++;
}
}
}
int main() {
int T;
char s[40];
cin.getline(s,40);
sscanf(s, "%d", &T);
while (T--) {
cin.getline(s, 40); // empty line
// prize
cin.getline(s, 40);
sscanf(s, "%lf", &purse);
REP(i, n_cut) {
cin.getline(s, 40);
sscanf(s, "%lf", &p[i]); //記錄總獎金和每個名次所得比例
}
// players
cin.getline(s, 40);
sscanf(s, "%d", &n);
assert(n <= 144);
REP(k, n) {
// read a 32-character line
cin.getline(s, 40);
// player name
strncpy(player[k].name, s, 20); //選手名字片林,小于20個字符
player[k].name[20] = 0;
player[k].amateur = 0;
if (strchr(player[k].name, '*')) { //如果有‘*’怀骤,標記為業(yè)余(amateur=1)
player[k].amateur = 1;
}
// scores
player[k].sc36 = player[k].sc72 = player[k].dq = 0;
memset(player[k].sc, -1, sizeof(player[k].sc));
REP(i, 4) {
// raw score
char t[5];
REP(j, 3) t[j] = s[20 + i * 3 + j]; t[3] = '\0'; /*前面20個字符為名字焕妙,后面四個成績焚鹊,隨時會有DQ,
用t[5]依次存儲每個成績研叫,t[0]為' '嚷炉,t[1],t[2]為成績申屹,t[3]為'\0'代表結束*/
// parse
if (!sscanf(t, "%d", &player[k].sc[i])) { /*當t[]存儲不為DQ,會返回1哗讥,結果為false杆煞,運行else决乎,記錄成績
當t[]存儲為DQ,會返回0娘摔,結果為ture凳寺,運行if
標記為DQ選手(dq=-1)肠缨,記錄犯規(guī)的場次晒奕,如果前兩場沒犯規(guī)脑慧,也記錄成績闷袒,
最后要break岩梳,因為犯規(guī)后不能再參加比賽*/
// DQ!
player[k].rnds = i;
player[k].dq = -1;
if (i < 2) player[k].sc36 = -1; //前兩輪有犯規(guī)冀值,說明已經(jīng)晉級不了,標記為-1
break; // skip other rounds (filled with -1, initially) //其他場次成績已經(jīng)用-1填充滑蚯,前面的memset()
}
else {
player[k].sc72 += player[k].sc[i];
if (i < 2)
player[k].sc36 += player[k].sc[i];
}
}
}
// round 1
sort(player, player + n, cmp1);
assert(player[n_cut - 1].sc36 >= 0);
/*檢測是否有更多選手晉級
用第70名選手前兩輪分數(shù)和后一位比較
如果相同膘魄,晉級選手加一乌逐,直到有不同分數(shù)的選手(已排序,不同則說明分數(shù)更差创葡,之后就不能晉級了)*/
for (int i = n_cut - 1; i < n; i++)
if (i == n - 1 || player[i].sc36 != player[i + 1].sc36) { n = i + 1; break; }
// round 2
sort(player, player + n, cmp2);
// print result
print_result();
if (T) printf("\n");
}
return 0;
}
void main4()
{
int i, j;
int a[10][10] = { 0 };
for (i = 1; i < 10; i++)
{
a[0][0] = 1;
a[i][0] = 1;
a[i][i] = 1;
for (j = 1; j < i; j++)
a[i][j] = a[i - 1][j - 1] + a[i - 1][j];
}
for (i = 0; i < 10; i++)
{
for (j = 0; j <= i; j++)
printf("%d ", a[i][j]);
printf("\n");
}
}
有個博客里有輸入輸出案例(題目沒有完整給)浙踢,可以自己測試https://blog.csdn.net/crazysillynerd/article/details/43763003
學到到的一些函數(shù):
1、sscanf(s,"%d",&T):sscanf將s中的字符串以整數(shù)的形式賦給T灿渴,這里是賦予比賽數(shù)量
? ? ?代碼中多次用到cin.getline(s, 40);sscanf(s, "%lf", &p[i]);
????可能會奇怪洛波,為什么不直接用cin>>p[i];
? ? 這是因為有時候會從緩沖區(qū)里讀到空格骚露,導致整個程序出錯
? ? ? ?有些地方可以換蹬挤,沒影響,但可能是為了整體風格一致棘幸,所以統(tǒng)一用了sscanf焰扳。
2、sprintf(t, "%d%c", rank, m > 1 && have_money && !player[i].amateur ? 'T' : ' '):
? ? ? sprintf的作用是將格式化的字符串輸出到一個目的字符串中吨悍,這里是先以整數(shù)賦予名次rank栽烂,再判斷該名次是否有并列選手,如果有就賦予字符T菇晃。之后輸出t估灿,就代表真正的名次了。
3汗销、assert(n <= 144):assert是一條檢查錯誤的語句,比如題目說不會超過144名選手宙枷。那么,當超過時,即n>144,這條語句就會終止程序苏潜,并給出錯誤信息(錯在哪一行)
如輸入n=150搀绣,執(zhí)行到這里會輸出Assertion failed: n <= 144,file (文件路徑)巧鸭,line (錯誤行數(shù))
不過題目一般說明不會超過144,那么系統(tǒng)測試數(shù)據(jù)就不會主動超過(除非人為輸入),就是說這條語句不寫應該也可以ac的,所以我不是很明白寫這條語句的意義沸版。
4细办、宏定義#define REP(i,n) for(int i = 0; i < (n); i++):這算是一個技巧娃殖,當代碼中多次要用到for循環(huán)時卧晓,一個REP(i,n)再改一下參數(shù)就可以搞定。不過這是我第一次遇到财破,理解代碼時反而會有些不適應俊性。不過,用到多次而相似的代碼時,確實可以用這個技巧宫峦。