游客 注册 | 登录
中文 | En

2138 - [贪心算法]排队接水

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

排队接水 water.pas/c/cpp

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

[输入格式] 

<span style="font-size:18px;">&nbsp;&nbsp;输入文件共两行，第一行为n；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。</span><br />

[输入格式] 

<span style="font-size:18px;">&nbsp; 输出文件有两行，第一行为一种排队顺序，即1到n的一种排列；第二行为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。&nbsp;</span><br />



<span style="font-size:18px;"><span style="font-size:18px;line-height:27px;">[输入样例]</span>water.in </span><br />

  10
  56 12 1 99 1000 234 33 55 99 812
[输出样例]water.out
  3 2 7 8 1 4 9 6 10 5
  291.90  

<br />


<br />

题目输入

题目输出

输入/输出样例

输入格式


                        

                        

                            
输出格式

                            

                        


                        
                                            


                                        
                    

						                                                        
                                                            
C++解答

                                
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std;
 
 struct scale
 {
 	int q;
 	int biao;
 }a[1500];
int s[1500];

 int  comp(const scale &a,const scale &b)
 {
 	if(a.q<b.q)return 1;
 	if(a.q>b.q)return 0;
 	if(a.biao<b.biao) return 1;
 	return 0;
 }
 
int main()
{
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
    	cin>>a[i].q;
    	a[i].biao=i;
    }
    sort(a+1,a+n+1,comp);
    for(int i=1;i<=n;++i)
    {
    	s[i]=a[i-1].q+s[i-1];
    	ans+=s[i];
    }
    double l=ans*1.0/n;
    for(int i=1;i<=n;++i)
    {
    	if(i!=n)printf("%d ",a[i].biao);
    	else printf("%d\n",a[i].biao);
    }
    printf("%.2lf",l);
    return 0;
}




                                                                                        
Java解答

                                
import java.util.*;
public class Main{
  public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);
    int n = cin.nextInt();
    Map<Integer,Integer> map = new TreeMap<Integer,Integer>();
    for(int i = 0; i < n; i ++){
      int value = cin.nextInt();
      map.put(i+1,value);
    }
    List<Map.Entry<Integer, Integer>> infoIds = new ArrayList<Map.Entry<Integer, Integer>>(map.entrySet());
		Collections.sort(infoIds, new Comparator<Map.Entry<Integer, Integer>>() {
			public int compare(Map.Entry<Integer, Integer> o1,
					Map.Entry<Integer, Integer> o2) {
				return (o1.getValue()).compareTo(o2.getValue());
			}
		});
    int sum = 0;
		for (int i = 0; i < infoIds.size(); i++) {
      if(i!=infoIds.size()-1){
        System.out.print(infoIds.get(i).getKey()+" ");
      }else{
        System.out.println(infoIds.get(i).getKey()+" ");
      }
      sum += infoIds.get(i).getValue()*(infoIds.size()-i-1);
    }
    double average = (double)sum/infoIds.size();
    String result = String.format("%.2f",average);
    System.out.println(result);
  }
}




                                                        
                                                                        
                    
                
                
            

            

                

                

                    

                        







                    


                    

                        请先登陆