东北小蟹蟹

[luogu p1223] 排队接水
题面传送门题目描述有n个人在一个水龙头前排队接水,假如每个人接水的时间为Ti,请编程找出这n个人排队的一种顺序,使...
扫描右侧二维码阅读全文
01
2019/10

[luogu p1223] 排队接水

题面

传送门
题目描述

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

输入格式

输入文件共两行,第一行为n;第二行分别表示第1个人到第n个人每人的接水时间T1,T2,…,Tn,每个数据之间有1个空格。

输出格式

输出文件有两行,第一行为一种排队顺序,即1到n的一种排列;第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。

输入输出样例

输入 #1
10 
56 12 1 99 1000 234 33 55 99 812

输出 #1
3 2 7 8 1 4 9 6 10 5
291.90

说明/提示

n<=1000
ti<=1e6,不保证ti不重复
当ti重复时,按照输入顺序即可(sort是可以的)

分析

一道非常经典的小学奥数题了,然而我没看出来,用dp做了半天???
首先,来明确一下等待时间(不包含本人接水时间)sum[i]的定义(sum是我自己定的):
sum[i] = sum[i-1] + t[i-1]
sum[0]自然是0啦,况且他前面没有人嘛。

答案要求的是平均等待时间,即
$\frac{t_0+t_1+t_2+\ldots+t_{i-1}}{n}$
n显然是定值。所以题目其实就是要求所有等待时间的和的最小值。

首先,用感性思维(我虽然很讨厌这个词,但我一时不知道怎么用别的词代替这个词。。。)思考一下:后面的人要等前面的人,那就让前面的人勤快点,后面的人等待时间不就短了?队列不就和谐快乐了?但是我们不啊
所以!将所有人的等待时间从小到大sort一下,就OK了。

好接下来我们用理性思维证明这个想法的正确性:
首先设一个队列,其中有两个人a[i],a[j],并且这个队列经过了如上所述的sort
大概是这样的:

那么,swap(交换)一下呢?

然而,a[i]<a[j],所以交换后的总等待时间变大了!!
完美地证明了方案的正确性。

代码

证明完毕,代码快来吧!
注意精度问题哦!

输出结果精确到小数点后两位。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
struct STU
{
    int t;
    int num;
}a[1005];//学生结构体:t代表等待时间,num代表编号。
bool cmp(STU a,STU b)
{
    if(a.t<b.t) return true;//按等待时间从小到大排序
    return false;
}//sort需要的函数
long long sum[1005],tot;//tot是答案,sum如题解上所述
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i].t);
        a[i].num=i+1;//由于i从0开始,本题从1开始,需要+1
    }
    sort(a,a+n,cmp);//快排
    printf("%d",a[0].num);
    for(int i=1;i<n;i++)
    {
        sum[i]=sum[i-1]+a[i-1].t;//等待时间递推式
        tot+=sum[i];//总等待时间
        printf(" %d",a[i].num);//顺便把编号输出了
    }
    printf("\n%.2lf",tot*1.0/n*1.0);//输出答案。注意精度!!!!!!否则9分惨案https://www.luogu.org/record/24536931
    return 0;
}

测评结果
over.

Last modification:October 1st, 2019 at 11:28 am
东北小蟹蟹已经穷的叮当都响不了啦!!qwq

Leave a Comment