[NOIP2007 普及组] 奖学金

 

这道题虽然我想到了和结构体，但没见过比较那么多的，一时间绷住了qwq（基础果然还要多练练）

#include
using namespace std;
int n;
struct stu{
	int cn, en, ma;
	int num;
	int sum;
}st[310];
bool cmp(stu a, stu b){
	if(a.sum > b.sum) return 1;
	else if(a.sum == b.sum && a.cn > b.cn) return 1;
    else if(a.sum == b.sum && a.cn == b.cn && a.num < b.num) return 1;
	else return 0;
}
int main(){
	cin >> n;
	for(int i = 1; i <= n; i ++ ){
		cin >> st[i].cn >> st[i].ma >> st[i].en;
		st[i].num = i;
		st[i].sum = st[i].cn + st[i].ma + st[i].en;
	}
	sort(st + 1, st + 1 + n, cmp);
	for(int i = 1; i <= 5; i ++ ){
		cout << st[i].num << " " << st[i].sum << endl;
	}
	return 0;
} 

---

P1012 [NOIP1998 提高组] 拼数 

#include
using namespace std;
int n;
string s[25];
bool cmp(const string &a, const string &b){
	return a + b > b + a;
}
int main(){
	cin >> n;
	for(int i = 0; i < n; i ++ ) cin >> s[i];
	sort(s, s + n, cmp);
	for(int i = 0; i < n; i ++ ) cout << s[i];
	return 0;
}

---

P1923 【深基9.例4】求第 k 小的数 

 woc这道题掉坑里了，题目求的是第k小的数不是排好序后第k个数

按样例来分析，已知最小的数是第0小，如果求的是第1小的数， 【1 2 3 4 5】数列中第1小的数应该是2，第k个数应该是1， 所以在输入k后要自加1

#include
using namespace std;
const int N = 5e6 + 10;
int a[N];
int n, k;
int quick_select(int a[], int l, int r, int k){
	if(l >= r) return a[l];
	int i = l - 1, j = r + 1, x = a[l + r >> 1];
	while(i < j){
		do i ++ ; while(a[i] < x);
		do j -- ; while(a[j] > x);
		if(i < j) swap(a[i], a[j]);
	}
	if(k <= j - l + 1) quick_select(a, l, j, k);
	else quick_select(a, j + 1, r, k - (j - l + 1));
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> k;
	k ++ ;
	for(int i = 0; i < n; i ++ ) cin >> a[i];
	cout << quick_select(a, 0, n - 1, k)<< endl;
	return 0;
}

---

P1068 [NOIP2009 普及组] 分数线划定

#include
using namespace std;
const int N = 5010;
int n, m;
struct stu{
	int num, score;
}st[N];
bool cmp(stu a, stu b){
	if(a.score > b.score) return true;
	else if(a.score == b.score && a.num < b.num) return true;
	else return false;
}
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i ++ ) cin >> st[i].num >> st[i].score;
	sort(st + 1, st + 1 + n, cmp);
	m = m * 1.5;
	int level = st[m].score;
	int cnt = m;
	for(int i = m + 1; i <= n && st[i].score == level; i ++ ){
		cnt ++ ; 
	}
	cout << level << " " << cnt << endl;
	for(int i = 1; i <= cnt; i ++ ){
		cout << st[i].num << " " << st[i].score << endl;
	}
	return 0;
}

---

P1781 宇宙总统 

 

 

这题a.sum.size() 的做法好骚啊 难绷

#include
using namespace std;
int n;
struct stu{
	int num;
	string sum;
}s[25];
bool cmp(stu a, stu b){
	if(a.sum.size() > b.sum.size()) return true;
	else if(a.sum.size() == b.sum.size() && a.sum > b.sum) return true;
	else return false;
}
int main(){
	cin >> n;
	for(int i = 1; i <= n; i ++ ){
		cin >> s[i].sum;
		s[i].num = i;
	}
	sort(s + 1, s + 1 + n, cmp);
	cout << s[1].num << endl;
	cout << s[1].sum << endl;
	return 0;
}