蓝桥杯算法提高排队打水问题（贪心排序+优先队列）-白红宇

蓝桥杯算法提高排队打水问题（贪心排序+优先队列）

阅读量：4139 次

发布时间：2019-05-25

本文共 720 字，大约阅读时间需要 2 分钟。

算法提高排队打水问题

时间限制：1.0s 内存限制：256.0MB

问题描述

　　有n个人排队到r个水龙头去打水，他们装满水桶的时间t1、t2………..tn为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？

输入格式

　　第一行n，r (n<=500,r<=75)

　　第二行为n个人打水所用的时间Ti (Ti<=100)；

输出格式

　　最少的花费时间

样例输入

2 

2 3 

样例输出

7   
  
      数据规模和约定  
    
  
      　　其中80%的数据保证n<=10  
    
     
     
    
     
   /*思路： 题目的意思是求所有人花费的时间和，等待时间也要算每次进队的人要加上前面出来的人的时间，也就是等待时间 刚开始看不清题目意思：理解成所有人排完水要多久贪心一下就是排序：大的先排，每次出队小的把大的进去现在题目意思是每个人累加算上等待最小，贪心要反过来 小的先排，不然后面等待的时间会变大 */#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;int a[500+10];priority_queue
          
           
            ,greater
            
              > q;int main(){ int n,r,i,re; while(cin>>n>>r){ re=0; for(i=0;i
             
              >a[i]; } sort(a,a+n); for(i=0;i