1. 题目回顾排队接水是洛谷上一道经典的贪心入门题P1223。题目大意是有n个人在一个水龙头前排队接水第i个人接水需要w[i]秒。每个人接水时后面的人都要等待。问如何安排接水顺序使得所有人接水时间的总和等待时间 接水时间最小并输出这个顺序和平均等待时间。2. 贪心思想为什么短任务优先先想一个生活场景银行柜台只有一个窗口前面排着两个人一个办业务要 10 分钟另一个只要 1 分钟。如果让 10 分钟的人先办那么 1 分钟的人要干等 10 分钟反过来1 分钟的人先办10 分钟的人只多等 1 分钟。显然让耗时短的人先办总等待时间更小。数学上可以证明任意交换两个相邻且前者耗时更长的人总等待时间都会下降所以最优解一定是按耗时从小到大排列。这就是贪心策略——每一步都让当前最短的任务先执行。3. 数据结构与排序structwater{intidx;// 人的编号从 1 开始intv;// 接水耗时}w[10005];这里用一个结构体把「编号」和「耗时」绑在一起因为排序后我们还要输出原来的编号顺序不能只排耗时而丢掉编号。boolcmp(water a,water b){if(a.v!b.v){returna.vb.v;// 耗时不同耗时小的排前面}returna.idxb.idx;// 耗时相同编号小的排前面保证稳定性}cmp是传给sort的比较函数第一关键字是耗时v第二关键字是编号idx。当两个人耗时一样时按编号升序这样输出结果确定、不会因排序不稳定而变。sort(w1,wn1,cmp);注意这里数组下标从1开始存所以排序范围是w[1]到w[n]对应w1到wn1左闭右开。4. 核心等待时间累加doublesum0;// 当前已经累计的等待时间doubleans0;// 总等待时间for(inti1;in;i){anssum;// 第 i 个人接水前他等待了 sum 秒sumw[i].v;// 他接完水后后面的人要多等 w[i].v 秒}这是全题最精妙的两行。我们模拟一下第 1 个人接水前等待0秒ans 0然后sum w[1].v第 2 个人接水前等待w[1].v秒ans w[1].v然后sum w[1].v w[2].v第 3 个人接水前等待w[1].v w[2].v秒ans ...依此类推。所以ans累加的是每个人接水前已经等待的总时长也就是题目要求的「等待时间总和」。5. 输出与平均等待时间for(inti1;in;i){coutw[i].idx ;// 按最优顺序输出每个人的原编号}coutendl;ansans/n;// 平均等待时间printf(%.2f,ans);// 保留两位小数输出先按排序后的顺序输出每个人的编号用空格隔开再计算平均等待时间ans / n最后用printf(%.2f)保留两位小数。6. 完整代码带注释#includebits/stdc.husingnamespacestd;structwater{intidx;// 编号intv;// 接水耗时}w[10005];boolcmp(water a,water b){if(a.v!b.v)returna.vb.v;// 耗时短优先returna.idxb.idx;// 耗时相同按编号}intmain(){intn;cinn;for(inti1;in;i){cinw[i].v;w[i].idxi;}sort(w1,wn1,cmp);// 按耗时升序排序doublesum0,ans0;for(inti1;in;i){coutw[i].idx ;// 输出最优顺序}coutendl;for(inti1;in;i){anssum;// 第 i 人等待时间sumw[i].v;// 更新后续等待}ansans/n;printf(%.2f,ans);// 平均等待时间保留两位小数return0;}7. 易错点提醒编号从 1 开始题目要求输出的是原编号不是排序后的位置所以结构体里必须存idx。排序范围数组从下标 1 开始存sort的区间是w1到wn1写错会漏排或越界。累加顺序一定是「先ans sum再sum w[i].v」顺序反了结果就错了。数据类型等待时间总和可能较大用double或long long累加避免溢出输出用printf(%.2f)保证两位小数。8. 小结这道题的核心就一句话让接水时间短的人先接水。排序 前缀等待累加即可在O(n log n)时间内求出最优顺序和平均等待时间。理解了这个贪心模型后面很多「任务调度」「排队优化」类题目都能触类旁通。
1. 题目回顾排队接水是洛谷上一道经典的贪心入门题P1223。题目大意是有n个人在一个水龙头前排队接水第i个人接水需要w[i]秒。每个人接水时后面的人都要等待。问如何安排接水顺序使得所有人接水时间的总和等待时间 接水时间最小并输出这个顺序和平均等待时间。2. 贪心思想为什么短任务优先先想一个生活场景银行柜台只有一个窗口前面排着两个人一个办业务要 10 分钟另一个只要 1 分钟。如果让 10 分钟的人先办那么 1 分钟的人要干等 10 分钟反过来1 分钟的人先办10 分钟的人只多等 1 分钟。显然让耗时短的人先办总等待时间更小。数学上可以证明任意交换两个相邻且前者耗时更长的人总等待时间都会下降所以最优解一定是按耗时从小到大排列。这就是贪心策略——每一步都让当前最短的任务先执行。3. 数据结构与排序structwater{intidx;// 人的编号从 1 开始intv;// 接水耗时}w[10005];这里用一个结构体把「编号」和「耗时」绑在一起因为排序后我们还要输出原来的编号顺序不能只排耗时而丢掉编号。boolcmp(water a,water b){if(a.v!b.v){returna.vb.v;// 耗时不同耗时小的排前面}returna.idxb.idx;// 耗时相同编号小的排前面保证稳定性}cmp是传给sort的比较函数第一关键字是耗时v第二关键字是编号idx。当两个人耗时一样时按编号升序这样输出结果确定、不会因排序不稳定而变。sort(w1,wn1,cmp);注意这里数组下标从1开始存所以排序范围是w[1]到w[n]对应w1到wn1左闭右开。4. 核心等待时间累加doublesum0;// 当前已经累计的等待时间doubleans0;// 总等待时间for(inti1;in;i){anssum;// 第 i 个人接水前他等待了 sum 秒sumw[i].v;// 他接完水后后面的人要多等 w[i].v 秒}这是全题最精妙的两行。我们模拟一下第 1 个人接水前等待0秒ans 0然后sum w[1].v第 2 个人接水前等待w[1].v秒ans w[1].v然后sum w[1].v w[2].v第 3 个人接水前等待w[1].v w[2].v秒ans ...依此类推。所以ans累加的是每个人接水前已经等待的总时长也就是题目要求的「等待时间总和」。5. 输出与平均等待时间for(inti1;in;i){coutw[i].idx ;// 按最优顺序输出每个人的原编号}coutendl;ansans/n;// 平均等待时间printf(%.2f,ans);// 保留两位小数输出先按排序后的顺序输出每个人的编号用空格隔开再计算平均等待时间ans / n最后用printf(%.2f)保留两位小数。6. 完整代码带注释#includebits/stdc.husingnamespacestd;structwater{intidx;// 编号intv;// 接水耗时}w[10005];boolcmp(water a,water b){if(a.v!b.v)returna.vb.v;// 耗时短优先returna.idxb.idx;// 耗时相同按编号}intmain(){intn;cinn;for(inti1;in;i){cinw[i].v;w[i].idxi;}sort(w1,wn1,cmp);// 按耗时升序排序doublesum0,ans0;for(inti1;in;i){coutw[i].idx ;// 输出最优顺序}coutendl;for(inti1;in;i){anssum;// 第 i 人等待时间sumw[i].v;// 更新后续等待}ansans/n;printf(%.2f,ans);// 平均等待时间保留两位小数return0;}7. 易错点提醒编号从 1 开始题目要求输出的是原编号不是排序后的位置所以结构体里必须存idx。排序范围数组从下标 1 开始存sort的区间是w1到wn1写错会漏排或越界。累加顺序一定是「先ans sum再sum w[i].v」顺序反了结果就错了。数据类型等待时间总和可能较大用double或long long累加避免溢出输出用printf(%.2f)保证两位小数。8. 小结这道题的核心就一句话让接水时间短的人先接水。排序 前缀等待累加即可在O(n log n)时间内求出最优顺序和平均等待时间。理解了这个贪心模型后面很多「任务调度」「排队优化」类题目都能触类旁通。
