codeforces Educational Codeforces Round 49 (Rated for Div. 2) C题

• 刚开始拿到这题很懵逼，知道了别人的思路之后开始写，但是还是遇到很多坑，要求求P^2/S最大。p=a b。就是求（a²+ b² +2ab)/ab最大，也就是a/b +b/a最大。那么题意就很明显了。
  但是处理的时候还要注意，刚开始用map存入数据，保存数量大于2的数据。接着就是找最小的，千万不要用数组进行双重循环查找，这样的O（n*n）会爆时，要先排序O(lgn);然后对相邻的遍历比较一遍就可以了O（n）。当数据量很大的时候差距很明显。
  附上ac代码（java）

package codeforces504;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/*
 * 贪心 数学 排序
 */
public class testC {

	public static void main(String[] args) throws IOException {
		// TODO 自动生成的方法存根
		StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		in.nextToken();
		int n=(int)in.nval;
		for(int i=0;i<n;i++)
		{ in.nextToken();int num=(int)in.nval; int a[]=new int[num]; Map<Integer,Integer>map=new HashMap(); for(int j=0;j<num;j++) { in.nextToken(); int q=(int)in.nval; if(map.containsKey(q)) {map.put(q, map.get(q)+1);} else map.put(q, 1); } int index=0;int a2=0;int b2=0; boolean b=false; for(int q:map.keySet()) { if(map.get(q)>=4) {a2=q;b2=q;b=true;break;} else if(map.get(q)>=2) {a[index++]=q;} } if(!b) { Arrays.sort(a,0, index);//0-到index-1排序  double min=Double.MAX_VALUE;; for(int q=0;q<index-1;q++) { double d=(double)a[q]/(double)a[q+1]+(double)a[q+1]/(double)a[q]; if(d<min) {min=d;a2=a[q];b2=a[q+1];} } } out.println(a2+" "+a2+" "+b2+" "+b2); out.flush();
		}
	}
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
 

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/82584658