【贪心算法】排队接水

洛谷P1223 排队接水

题目描述

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

输入格式

第一行为一个整数 $n$。

第二行 $n$ 个整数，第 $i$ 个整数 $T_i$ 表示第 $i$ 个人的接水时间 $T_i$。

输出格式

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

样例 #1

样例输入 #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

提示

$1\le n\le 1000$，$1\le t_i\le 10^6$，不保证 $t_i$ 不重复。

分析

想了半天，其实就是冒泡算法，甚至你可以用sort…
分类到了贪心算法，求局部最优解，这个等待时间最短的除了从小到大排序以外就没有其他最优解了，因为前面每个都要累加，如果前面就很大的数了，后面累加起来很明显就不对。

这里我犯了很大的错误，我用s=1 + 1+2 + 1+2+3 + … + 1+2+3+…+n 的思想，却没想到最后的人不用等…脑子瓦特了，纠错纠了半天。

#include<bits/stdc++.h>
using namespace std;
int main(){
//freopen("t1.in","r",stdin);
//freopen("t1.out","w",stdout);
long i,j,n,a[1005],b[1005];
double s=0,c=0;
cin>>n;
for(i=0;i<n;i++){
cin>>a[i];
b[i]=i+1;
}
for(i=0;i<n-1;i++){
for(j=0;j<n-i-1;j++){
if(a[j]>a[j+1]){
swap(a[j],a[j+1]);
swap(b[j],b[j+1]);
}
}
}
for(i=0;i<n;i++){
cout<<b[i]<<" ";
}
cout<<endl;
for(i=0;i<n-1;i++){//这里要注意是n-1，最后一个人不用等
c=c+a[i];
   s=s+c;
}
printf("%.2f",s/n);
}

当然最后累加那里，可以换成别的

for(i=0;i<n;i++){
        a[i]*=(n-i-1);
        s+=a[i];
    }

原文地址：https://blog.csdn.net/weixin_45795497/article/details/137673322

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！