算法设计与分析——贪心算法——单个出水口打水问题

电玩女神 2022-10-15 12:56 133阅读 0赞

1.打水问题：有n个人去水房排队打水，只有一个出水口，且出水口流速恒定。每个人因为盛水的工具不一，打水所需的时间也不一致，设第i个人所需要的打水时间为ti；问如何安排打水顺序使得所有人的平均等待时间最短。

#include<iostream>
    #include<bits/stdc++.h>
    using namespace std;
    
    typedef struct Node
    {
        
    	int i;
    	int time;
    }node;
    
    bool cmp(node x,node y)
    {
        
    	if(x.time<y.time)
    		return true;
    	else 
    		return false;	
    }
    int solue(int n,int time_i[])
    {
        
    	Node node[n];
    	for(int i=1;i<=n;i++)
    	{
        
    		node[i].i=i;
    		node[i].time=time_i[i];
    	}
    	sort(node+1,node+n+1,cmp);//从小到大排序 
    
    		
    	int waittime[n+1];
    	int wait_time_all=0;
    	waittime[1]=0;
    	wait_time_all+=0;
    	for(int i=2;i<=n;i++)
    	{
        
    	waittime[i]=waittime[i-1]+node[i-1].time;//某一个人的等待时间是上前一个人打水的时间加上前前一个的等待时间和 
    	wait_time_all+=waittime[i];
    	}
    	
    	return wait_time_all;
    	
    }
    int main()
    {
        
    	int n;
    	cout<<"输入正在排队打水的人数：";
    	cin>>n;
    
    	int time_i[n+1];
    	cout<<"输入正在排队的人每个人所需的打水时间："<<endl; 
    	for(int i=1;i<=n;i++)
    	{
        
    		cin>>time_i[i];
    	}
    
    	
    	
    	cout<<(float)solue(n,time_i)/n;
    }

![在这里插入图片描述][20210525130844751.png]

[20210525130844751.png]: /images/20221014/c3aaf3e639704bea8b79dff255bf6ee1.png