课堂复习笔记

一、结构体与多关键字排序

1. 为什么使用结构体

当一个对象同时有多个信息时，可以把这些信息放进同一个结构体中。

例如，一名学生有姓名、三科成绩和总分：

struct node{
	string name;
	int chinese,math,english,total;
}a[1005];

这样排序后，学生的所有信息会一起移动，不会出现姓名和成绩错位的问题。

经典用法：

• 学生成绩排名
• 比赛选手排名
• 商品按价格、销量排序
• 文件按扩展名和文件名整理
• 记录原编号，排序后再恢复原顺序

2. 多关键字排序

比较两条记录时，要按照题目给出的优先级逐项比较。

bool cmp(node x,node y){
	if(x.total!=y.total){
		return x.total>y.total;
	}else if(x.chinese!=y.chinese){
		return x.chinese>y.chinese;
	}else if(x.name!=y.name){
		return x.name<y.name;
	}
	return false;
}

判断顺序：

1. 先比较最重要的条件。
2. 第一项相同，再比较第二项。
3. 所有条件都相同，返回 false。

3. 比较函数的三个规则

规则一：升序用 <，降序用 >

return x.score>y.score; // 分数从大到小
return x.name<y.name;   // 姓名从小到大

规则二：不要使用 <= 或 >=

两个对象完全相同时，不能说其中一个一定排在另一个前面。

规则三：最后必须返回结果

这两天多段代码出现了下面的警告：

control reaches end of non-void function

原因是所有字段都相等时，比较函数没有执行 return。正确写法是在最后补上：

return false;

4. 排序范围必须与下标一致

数组从 0 开始存：

for(int i=0;i<n;i++) cin>>a[i].score;
sort(a,a+n,cmp);

数组从 1 开始存：

for(int i=1;i<=n;i++) cin>>a[i].score;
sort(a+1,a+n+1,cmp);

不能一边从 1 开始存，一边使用 sort(a,a+n,cmp)。这会漏掉最后一项，还会把没有使用的 a[0] 排进去。

5. 排序相关易错点

• 每一层排序方向都要重新看题目，不能全部写成降序。
• 原编号通常写成 id=i 或 id=i+1，要与循环起点一致。
• 输出内容和顺序要逐项核对，不能多输出或少输出字段。
• 写完 return 后检查分号，P223 曾因少一个分号编译错误。
• 比较胜率时不要直接用整数除法，应使用交叉相乘。

比较 a/b 与 c/d：

long long left=1LL*a*d;
long long right=1LL*c*b;

这样没有小数误差，也不会被整数除法截断。

---

二、贪心算法

1. 贪心的基本想法

贪心算法每一步都选择当前最合适的方案，并把当前状态更新好，再继续处理后面的数据。

做贪心题时先回答三个问题：

1. 每一步应该优先选择什么？
2. 选择之后，哪个状态发生了变化？
3. 数据是否需要先排序？

2. 选择后必须更新状态

在“糖果”题中，选择了一个新的位置后，要把它记录成新的上一个位置。

int last=a[0],ans=1;
for(int i=1;i<n;i++){
	if(a[i]-last>=m){
		ans++;
		last=a[i]; // 选择成功后更新位置
	}
}

常见错误是只增加答案，却没有更新 last。这样后面的判断会一直与第一个位置比较。

3. 面额兑换

面额可以使用任意次，并且题目中的面额适合从大到小选择时，可以依次取尽量多的大面额。

int money[6]={100,50,20,10,5,1};
for(int i=0;i<6;i++){
	int cnt=n/money[i];
	n%=money[i];
}

经典用法：

• 最少纸币数量
• 按单位从大到小拆分
• 时间、长度等单位换算

注意：不是所有面额都能直接贪心。只有能够证明“大面额优先不会让答案变差”时才能使用。

4. 部分背包

物品允许只取一部分时，应优先选择单位重量价值最高的物品。

struct node{
	int w;
	double price;
}a[10005];

bool cmp(node x,node y){
	return x.price>y.price;
}

处理过程：

double ans=0;
for(int i=0;i<n;i++){
	if(capacity>=a[i].w){
		ans+=a[i].w*a[i].price;
		capacity-=a[i].w;
	}else{
		ans+=capacity*a[i].price;
		break;
	}
}

经典用法：

• 物品可以切分的最大收益
• 固定容量下优先装单位价值高的物品
• 金银岛、部分背包类问题

5. 最小满足匹配

有一组需求和一组资源，每个需求要分配一个不小于它的资源，并希望总消耗最小时：

1. 两组数据分别从小到大排序。
2. 从最小需求开始找。
3. 当前资源太小，就换下一个资源。
4. 当前资源能满足需求，就完成匹配，两个指针同时移动。

sort(a,a+n);
sort(b,b+m);
int l=0,r=0;
long long ans=0;
while(l<n&&r<m){
	if(b[r]<a[l]){
		r++;
	}else{
		ans+=b[r];
		l++;
		r++;
	}
}
if(l<n) cout<<-1;
else cout<<ans;

常见错误是把 b 数组写成 sort(b,b+n)。如果 b 的长度是 m，正确范围应为 sort(b,b+m)。

---

三、双指针

1. 两数之和

数组排序后：

• 左指针指向最小值。
• 右指针指向最大值。
• 和太小，左指针右移。
• 和太大，右指针左移。
• 和等于目标值，找到答案。

sort(a,a+n);
int l=0,r=n-1;
bool found=false;
while(l<r){
	long long sum=1LL*a[l]+a[r];
	if(sum<target){
		l++;
	}else if(sum>target){
		r--;
	}else{
		found=true;
		break;
	}
}
cout<<(found?"YES":"NO")<<endl;

这道题连续错误的主要原因：

• 忘记排序。
• 右指针从 1 开始。
• 右指针写成 n，访问了数组外的位置。
• 和太小时移动了错误的指针。

最重要的初值：

int l=0,r=n-1;

2. 双指针的经典用法

• 有序数组中寻找两个数的和
• 两个有序数组进行匹配
• 删除重复元素
• 维护一段连续区间

使用双指针前，要先判断数据是否需要排序，并明确每个指针代表什么。

---

四、模拟、边界与输出

1. 变量必须初始化

局部变量不会自动变成 0。

错误写法：

int p1,p2;
p1+=a[i];

正确写法：

int p1=0,p2=0;

2. 循环下标要统一

“蜡烛”题前两次错误与下标有关。建议同一道题统一使用一种下标方式，不要在不同循环中混用 0 和 1。

每次写循环时检查：

• 第一个有效位置是多少？
• 最后一个有效位置是多少？
• 排序范围是否一致？
• 循环中是否可能访问 a[n]？

3. 小数输出要按题意

“出租车费”经过多次修改才通过，主要问题是计算规则和输出格式。

如果结果是整数，就只输出整数；否则保留一位小数：

double ans=...;
int x=ans;
if(x==ans){
	cout<<x<<endl;
}else{
	cout<<fixed<<setprecision(1)<<ans<<endl;
}

计算时也要区分：

• 起步价
• 完整优惠段
• 剩余距离
• 剩余部分单独乘坐还是再买一个完整优惠段

4. 数组长度写对

两个数组长度分别为 n 和 m 时：

sort(a,a+n);
sort(b,b+m);

不要因为两个数组写在同一道题中，就默认它们长度相同。

---

五、写完代码后的检查顺序

建议每次提交前按下面顺序检查：

1. 输入变量和题目是否一一对应。
2. 数组从 0 还是从 1 开始。
3. sort 的左右范围是否正确。
4. 比较函数是否覆盖所有情况，最后是否 return false。
5. 贪心选择后是否更新了状态。
6. 双指针是否从 0 和 n-1 开始。
7. 局部变量是否初始化。
8. 输出字段、空格、换行和小数位是否符合题意。
9. 用最小数据、相等数据和边界数据各检查一次。

六、本次复习重点

优先复习顺序：

1. 多关键字比较函数的完整写法
2. 数组下标与排序范围
3. 贪心选择后的状态更新
4. 两数之和的标准双指针
5. 小数计算与输出格式