打水问题（贪心）

一、打水问题

问题描述

　　N个人要打水，有M个水龙头，第i个人打水所需时间为Ti，请安排一个合理的方案使得所有人的等待时间之和尽量小。

输入格式

　　第一行两个正整数N M 接下来一行N个正整数Ti。
　　N,M<=1000，Ti<=1000

输出格式

　　最小的等待时间之和。（不需要输出具体的安排方案）

样例输入

7 3
3 6 1 4 2 5 7

样例输出

11

提示

　　一种最佳打水方案是，将N个人按照Ti从小到大的顺序依次分配到M个龙头打水。
　　例如样例中，Ti从小到大排序为1，2，3，4，5，6，7，将他们依次分配到3个龙头，则去龙头一打水的为1，4，7；去龙头二打水的为2,5；去第三个龙头打水的为3,6。
　　第一个龙头打水的人总等待时间 = 0 + 1 + (1 + 4) = 6
　　第二个龙头打水的人总等待时间 = 0 + 2 = 2
　　第三个龙头打水的人总等待时间 = 0 + 3 = 3
　　所以总的等待时间 = 6 + 2 + 3 = 11

#include
#include
#include
using namespace std;
const int N=1100;
int t[N];  //每一个人打水所需时间 
int waite[N];  //存放的是每一个人需要等的时间 
int n,m; //n个人，m个水龙头
int main()
{cin>>n>>m;for(int i=0;i>t[i]; /*此题使用的是贪心思想，你可以想象一下，当你在打水的时候你是不是都在想，如果你前面的人的打水时间越少你是不是就能更快的打到水了。题目要求的是最小的等待时间之和，因此只需要按照这个思路去操作 即可。我们可以对所有的打水时间先进行排序，打水时间少的先打水，后面的人就不用等很长时间了。你可以想象一下如果你的前面是打水时间为1分钟的，你是不是要等1分钟，如果你的前面是打水时间为7分钟的，那你是不是要等7分钟，所以你更愿意你的前面是谁呢？显然是1分钟的呀 */ sort(t,t+n);//先排序/*现在我们就开始算每个人需要等待的时间是多少，我的思路是 你的等待时间=前面一个人的等待时间+前面一个人的打水时间然后把每个人的等待时间加起来就得到了最少的时间 */ //把n个人分别分配到m个水龙头上 int ans=0;  // 最小的等待时间之和for(int i=0;i

7 

#include
#include
#include
using namespace std;
const int N=1100;
int t[N];  //每一个人打水所需时间 
int waite[N];  //存放的是每一个人需要等的时间 
int n,m; //n个人，m个水龙头
int main()
{cin>>n>>m;for(int i=0;i>t[i]; /*此题使用的是贪心思想，你可以想象一下，当你在打水的时候你是不是都在想，如果你前面的人的打水时间越少你是不是就能更快的打到水了。题目要求的是最小的等待时间之和，因此只需要按照这个思路去操作 即可。我们可以对所有的打水时间先进行排序，打水时间少的先打水，后面的人就不用等很长时间了。你可以想象一下如果你的前面是打水时间为1分钟的，你是不是要等1分钟，如果你的前面是打水时间为7分钟的，那你是不是要等7分钟，所以你更愿意你的前面是谁呢？显然是1分钟的呀 */ sort(t,t+n);//先排序/*现在我们就开始算每个人需要等待的时间是多少，我的思路是 你的等待时间=前面一个人的等待时间+前面一个人的打水时间然后把每个人的等待时间加起来就得到了最少的时间 */ //把n个人分别分配到m个水龙头上 int ans=0;  // 最小的等待时间之和for(int i=0;i

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！