【洛谷】P1223 排队接水 题解

这道题首先要明确一处细节，一个人的等待时间并不包括他本身为自己打水的时间（即只记录别人打水的总时间）

首先，若使n个人的平均等待时间最小，不难想出，应让用时较短的人先打水，主体思想即此。

​ 所以首先进行预处理，将每人的时间从小到大sort排序。

① 要输出排队顺序，所以用结构体可以方便的表示和进行数据处理：一个变量表示序号，另一个为接水时间

② 输出平均等待时间：因为第一个人等待时间为0，所以从a2开始加，因此总时间s为

​ a2

​ +a2+a3

​ +a2+a3+a4

​ +…

​ +a2+a3+…+an

归纳得

s = a2*(n-1)+a3*(n-2)+…+an*1

ac代码如下：

#include
#include
#include
using namespace std;
int n;
double s = 0;
struct aaa {int x, y; //序号，时间
}a[1010];
void sum() {}
bool cmp(aaa c, aaa d)
{if (c.y != d.y)return c.y < d.y;return c.x < d.x;
}
int main() {cin >> n;for (int i = 1; i <= n; i++){cin >> a[i].y;a[i].x = i;}sort(a + 1, a + n + 1,cmp);//总排队时间int ans = n-1;for (int j = 1; j <= n-1; j++){s += a[j].y * ans;--ans;}for (int i = 1; i <= n; i++)cout << a[i].x << " ";cout << endl;cout << setprecision(2) << fixed << s / n;return 0;
}