20241022每日一题洛谷P1223

从0.5开始的C语言学习 / 2024-11-09 / 原文

普及洛谷 P1223 接水问题

有 n个人在一个水龙头前排队接水，假如每个人接水的时间为 T_i，请编程找出这 n 个人排队的一种顺序，使得 n 个人的平均等待时间最小

第一行为一个整数 n, 第二行 n个整数，第 i个整数 T_i表示第 i个人的接水时间 T_i

输出两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）

不同于贪心的模板接水问题，我们需要输出排队的顺序

使用结构体把排队时间和顺序进行绑定可以有效的解决问题

struct peop
{
	int time;
	int num;
};

peop a[1010];

在主函数中，我们依次读入 a数组的 time 和 num

按照贪心的想法，每次选取用时最短的人来接水

所以需要对 a数组中的 time 进行从小到大的排序

问题来了，单纯按照 time 进行排序后 num 的顺序会对应不上 time

这是因为结构体中的元素不能进行整体的排序

我们需要一种方法来使得结构体按照它的某一个元素的大小，来对结构体整体进行排序

这就引入了 sort 函数的 cmp 参数

sort(first_pointer,first_pointer+n,cmp);

通过`cmp`参数实现结构体的排序：

cmp 比较函数需要接受两个参数并返回一个bool值，如果第一个参数应该排在前面，就返回 true；否则返回 false

例：配置 cmp 进行降序排序

bool cmp(int a, int b) {
    return a > b; // 降序排序
}

下面来逐步解释这一函数：

传入cmp函数的两个参数为 a 和 b ,我们想让大的数排在前面

返回为 ture 时，表示 a 这个参数应该排在前面，显然符合 a > b的逻辑

返回为 false 时，表示 a 这个参数应该排在后面，a > b不成立，符合逻辑

关于这道题，我们需要配置一个cmp函数使得结构体根据结构体中的一个元素进行排序

有：

bool cmp(peop x, peop y) {
    return x.time < y.time;//按照time大小进行升序
}

传入cmp函数的两个参数为结构体x 和结构体y ，我们想让time最小的结构体排在前面

当第一个参数的time小于第二个参数的time时，返回ture，即把第一个参数放在前面

在配置好适用于这道题的cmp函数后

通过：

sort(a,a+n,cmp);

就可以peop进行整体排序

补充：lambda表达式

Lambda 表达式是一种简洁的方式来定义一个匿名函数

语法如下：

[capture](parameters) -> return_type {// function body}
/*
capture：用于捕获外部变量，可以是值捕获或引用捕获
parameters：参数列表，可以省略参数的类型
return_type：返回的类型，如果可以推断则可以省略
function body：函数体，包含要执行的代码
*/

关于这道题的cmp配置，我们可以简单的使用lambda表达式填入：

sort(a+1, a + n+1, [](peop i, peop j) {return i.time < j.time; });

相当于：

bool cmp(peop i, peop j) {
    return i.time < j.time;//按照time大小进行升序
}

关于lambda表达式的推广运用，先挖个坑以后再来填

这道题完整代码如下：

struct peop
{
	int time;
	int num;
};

peop a[1010];
int b[1010],n;
double sum;

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i].time);
		a[i].num = i;
	}
	sort(a+1, a + n+1, [](peop i, peop j) {return i.time < j.time; });
	for (int i = 1; i <= n; i++) {
		printf("%d ", a[i].num);
		b[i] = b[i - 1] + a[i].time;
		if (i<n) sum += b[i];
	}
	printf("\n%.2lf", sum / n * 1.0);
	return 0;
}