前两次课程作业与主题

复杂度分析

首先理解一个概念：基本操作 意指不能再分的操作，如 x++, --x, cout。

假设一个程序中基本操作的次数为：$f(n) = \frac{1}{2}n^2 + 2n+3$.

随着 $n$ 的不断扩大，我们发现 $f(n)$ 的值越趋近于 $n^2$，所以我们就称该程序的渐进时间复杂度为 $O(n^2)$，这种方式被称为大O记法。

排序

$O(n^2)$ ：冒泡、选择、插入

$O(n)$： 计数（桶排序和计数排序还是有区别的，计数排序是桶排序桶距为1的特例）

$O(n logn)$：快速、归并、堆排序

排序笔记

实际应用

实际上使用的时候，都直接sort了，管你什么排序（旁白：sort这么牛嘛）。

对于不同的问题可能会利用插入，计数、堆排序进行优化，具体要结合实际分析。

上课代码

#include<bits/stdc++.h> 
using namespace std;
const int N=110;
struct T{
	string name;
	int s1,s2;
	char c1,c2;
	int num,id;
	int sum(){
		int money = 0;
		if(s1 > 80 && num >= 1) money += 8000;
		if(s1 > 85 && s2 > 80) money += 4000;
		if(s1 > 90) money += 2000;
		if(s1 > 85 && c2=='Y') money += 1000;
		if(s2 > 80 && c1=='Y') money += 850;
		return money;
	}
}a[N];
bool cmp(T a, T b){
	if(a.sum() != b.sum()) return a.sum() > b.sum();
	return a.id < b.id; 
}
void solve(){
	int n; cin>>n; 
	string name;
	int s1,s2; char c1,c2; int num;
	for(int i=0; i<n; i++) {
		cin>>name>>s1>>s2>>c1>>c2>>num;
		a[i] = {name, s1,s2,c1,c2,num,i};
	}
	sort(a, a+n, cmp);
	cout<<a[0].name<<endl<<a[0].sum()<<endl;
	int money = 0;
	for(int i=0; i<n; i++) money += a[i].sum();
	cout<<money<<endl;
}
int main(){
	freopen("scholar.in", "r", stdin);
	freopen("scholar.out", "w", stdout);
	solve();
	fclose(stdin), fclose(stdout);// 
	return 0;// C++11 
}