排队接水-贪心算法 一直没通过

Question

我的程序一直Wrong Answer，不知道问题出在哪里？希望帮忙解答！🙏

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;

struct Person{
    int id;
    int time;
};

bool compare(const Person &a,const Person &b){
    if(a.time==b.time){
        return a.id<b.id;
    }
    return a.time<b.time;
}    

int main(){
    int T;
    cin>>T; // 测试数据组数
    
    while(T--){
        int n;
        cin>>n;
        vector<Person> people(n);
        
        // 输入每个人的接水时间
        for(int i=0;i<n;i++){
            people[i].id=i+1;
            cin>>people[i].time;
        }
        
        // 排序
        sort(people.begin(),people.end(),compare);
        
        // 输出排队顺序
        for(int i=0;i<n;i++){
            cout<<people[i].id;
            if(i != n-1) cout<<" ";
        } 
        cout<<endl;
        
        long long sum=0;
        for(int i=0;i<n;i++){
            sum+=(long long)people[i].time*(n-i-1);
        }
        
        printf("%.2f",sum*1.0/n);
    }
    
    return 0;
}

Answer 1

晚上好🌙🌙🌙
本答案参考通义千问

你的程序在“排队接水”问题中一直 Wrong Answer，主要问题是 逻辑错误 和 输出格式不正确。我们来逐步分析问题，并给出解决方案。

---

✅ 问题分析

1. 题目要求

题目是经典的贪心算法问题：排队接水，要求将所有人按接水时间从小到大排序，若时间相同则按编号从小到大排序。然后计算每个人的等待时间总和的平均值。

例如：
如果有 3 个人，他们的接水时间分别是 1, 2, 3。
排队顺序是 1 → 2 → 3。
那么：

• 第一个人等待时间为 0（自己接水）
• 第二个人等待时间为 1
• 第三个人等待时间为 1+2 = 3
  总等待时间 = 0 + 1 + 3 = 4
  平均等待时间 = 4 / 3 = 1.33

---

❌ 你代码的问题

1. sum 计算错误

sum += (long long)people[i].time * (n - i - 1);

这个公式是 错误的，它计算的是所有后续人等待的时间总和，而不是每个人自己的等待时间。

正确的做法是：
每个人等待时间 = 前面所有人的接水时间之和

---

✅ 正确的解题思路

1. 排序方式

• 按照接水时间从小到大排序，如果时间相同，则按编号从小到大排序。

2. 计算每个人的等待时间

• 从第 0 个开始，每个人等待时间 = 前面所有人的接水时间之和。
• 累加所有等待时间，最后求平均。

---

✅ 修改后的代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;

struct Person {
    int id;
    int time;
};

bool compare(const Person &a, const Person &b) {
    if (a.time == b.time) {
        return a.id < b.id;
    }
    return a.time < b.time;
}

int main() {
    int T;
    cin >> T; // 测试数据组数

    while (T--) {
        int n;
        cin >> n;
        vector<Person> people(n);

        // 输入每个人的接水时间
        for (int i = 0; i < n; i++) {
            people[i].id = i + 1;
            cin >> people[i].time;
        }

        // 排序
        sort(people.begin(), people.end(), compare);

        // 输出排队顺序
        for (int i = 0; i < n; i++) {
            cout << people[i].id;
            if (i != n - 1) cout << " ";
        }
        cout << endl;

        // 计算等待时间总和
        long long total_wait_time = 0;
        long long current_time = 0;

        for (int i = 0; i < n; i++) {
            total_wait_time += current_time;
            current_time += people[i].time;
        }

        // 计算平均等待时间并输出
        double average = static_cast<double>(total_wait_time) / n;
        cout << fixed << setprecision(2) << average << endl;
    }

    return 0;
}

---

✅ 重点部分总结

1. 排序逻辑正确：使用 compare 函数按照时间升序、编号升序排列。
2. 等待时间计算方式正确：
   • 每个人的等待时间 = 前面所有人接水时间之和。
   • 使用 current_time 变量累加前面的人的接水时间。
3. 输出格式正确：
   • 使用 fixed 和 setprecision(2) 来控制小数点后两位。

---

✅ 示例输入与输出

输入：

1
3
1 2 3

输出：

1 2 3
1.33

---

如果你还有其他测试用例或疑问，欢迎继续提问！希望这能帮你解决问题 😊