2016网易研发编程题解析

发表于   |   分类于   |     |   阅读次数

enter description here

奖学金

小v今年有n门课，每门都有考试，为了拿到奖学金，小v必须让自己的平均成绩至少为avg。
每门课由平时成绩和考试成绩组成，满分为r。现在他知道每门课的平时成绩为ai ,
若想让这门课的考试成绩多拿一分的话，小v要花bi 的时间复习，不复习的话当然就是0分。
同时我们显然可以发现复习得再多也不会拿到超过满分的分数。为了拿到奖学金，小v至少要花多少时间复习。

输入描述： 第一行三个整数n,r,avg(n大于等于1小于等于1e5，r大于等于1小于等于1e9,avg大于等于1小于等于1e6)，
接下来n行，每行两个整数ai和bi，均小于等于1e6大于等于1

输入例如：

5 10 9
0 5
9 1
8 1
0 1
9 100

输出例如：

43

代码：

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
public class Wangyi_4 {
/**
 * 思路：对第i门课程，如果要增加1分，需要花费bi个小时的时间，为了耗费的时间最小，
 * 我们肯定应该选那些增加1分所用时间短的课程复习。
 *代码步骤：先以bi(也就是以样例中的时间列)为排序基准，对由ai和bi组成的矩阵(二维数组)由小到大排序，
 *然后逐步由花费时间最小的课程开始(也就是排序后的第一行)逐步增加1分，判断总分数是否到了avg*n，到了就停止，
 *否则继续加1分。
 * @author_LYF
 */
	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		while(scanner.hasNext()){
			int n=scanner.nextInt();
			long r=scanner.nextLong();
			long avg=scanner.nextLong();
			//二维数组[bi,ai]，以bi为key排序；n行2列
			int[][] arr=new int[n][2];
			for(int i=0;i<n;i++){
				arr[i][0]=scanner.nextInt();
				arr[i][1]=scanner.nextInt();
			}
			
			//check读入是否正确
//			System.out.println(n+"\r"+r+"\r"+avg);
//			for(int i=0;i<n;i++){
//				System.out.println(Arrays.toString(arr[i]));
//			}
			
			long total=n*avg;//要大于这个总数total，才可以
			//按bi时间重新排序数组
			sortArr(arr,n);
			
			long grades=0;//成绩总和
			for(int i=0;i<n;i++)
				grades+=arr[i][0];
			
			long times=0;//补课时间
			int i=0;//i门功课
			while(grades<total&&i<n){
				//第i门课未达到满分时
				if(arr[i][0]<r){
					grades++;
					times+=arr[i][1];
					arr[i][0]+=1;
				}else{
					i++;
				}
			}
			System.out.println(times);
		}
		scanner.close();
	}
	/**
	 * 按二维数组的第二列作为关键字，从小到大重新排列数组
	 * @param arr
	 */
	public static void sortArr(int[][] arr,int row){
		//冒牌排序
		for(int i=0;i<row-1;i++){
			for(int j=i+1;j<row;j++){
				if(arr[i][1]>arr[j][1]){
					//交换i行和j行对应两个数
					int tmp1=arr[i][0];
					arr[i][0]=arr[j][0];
					arr[j][0]=tmp1;
					
					int tmp2=arr[i][1];
					arr[i][1]=arr[j][1];
					arr[j][1]=tmp2;
				}
			}
		}
	}
}

路灯

一条长l的笔直的街道上有n个路灯，若这条街的起点为0，终点为l，第i个路灯坐标为ai，每盏灯可以覆盖到的最远距离为d，为了照明需求，所有灯的灯光必须覆盖整条街，但是为了省电，要是这个d最小，请找到这个最小的d

输入描述： 每组数据第一行两个整数n和l（n大于0小于等于1000，l小于等于1000000000大于0）。
第二行有n个整数(均大于等于0小于等于l)，为每盏灯的坐标，多个路灯可以在同一点。

输入例子：

7 15
15 5 3 7 9 14 0

输出例子：

2.5

代码：

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
public class Wangyi_5 {
/**
 * 思路：找到路灯坐标相差最大的,然后除以2即可,不是很难，但是有坑，留意脚下。
 * 特别注意边界情况，也就是路灯不在两段点上，也要确保能照到。就是说边界距离也要考虑
 * 注意的是，打印的数要带两位小数
 * @author henry_LYF
 */
	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		//读入数据
		while(scanner.hasNext()){
			int n=scanner.nextInt();//路灯总数
			int l=scanner.nextInt();//街道长度
			ArrayList<Integer> loc=new ArrayList<Integer>(n);//存放路灯坐标
			for(int i=0;i<n;i++){
				loc.add(scanner.nextInt());
			}
			
			//排序数组
			Collections.sort(loc);
			//System.out.println(loc);
			//边界情况，最后一段距离
			int disLast=l-loc.get(n-1);
			//最前面一段距离
			int disFront=loc.get(0);
			//返回两路灯的最大距离
			int maxBetween=maxDistance(loc);
			//则比较上述三者
			int max=maxBetween>disLast?(maxBetween>disFront?maxBetween:disFront):(disLast>disFront?disLast:disFront);
			
			System.out.println(String.format("%.2f", max/2.0));
		}
		scanner.close();
	}
	/**
	 * 返回已排序数组中，相邻最大的距离
	 * @param loc
	 * @return
	 */
	public static int maxDistance(ArrayList<Integer> loc){
		int len=loc.size();
		int maxDis=0;//最大距离
		for(int i=0;i<len-1;i++){
			if(loc.get(i+1)-loc.get(i)>maxDis){
				maxDis=loc.get(i+1)-loc.get(i);
			}
		}
		return maxDis;
	}
}

热评文章