Winter Vacation Training(5st Week)

7-2 寻找大富翁 (25分)

胡润研究院的调查显示，截至2017年底，中国个人资产超过1亿元的高净值人群达15万人。假设给出N个人的个人资产值，请快速找出资产排前M位的大富翁。

输入格式:

输入首先给出两个正整数N（≤10​6​​）和M（≤10），其中N为总人数，M为需要找出的大富翁数；接下来一行给出N个人的个人资产值，以百万元为单位，为不超过长整型范围的整数。数字间以空格分隔。

输出格式:

在一行内按非递增顺序输出资产排前M位的大富翁的个人资产值。数字间以空格分隔，但结尾不得有多余空格。

输入样例:

8 3
8 12 7 3 20 9 5 18

输出样例:

20 18 12

 思路：

无AC思路

代码：

后两个点格式错误，内存超限

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws IOException {
 		// TODO 自动生成的方法存根
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String str[]=br.readLine().split(" ");
        int N=Integer.parseInt(str[0]);
        int M=Integer.parseInt(str[1]);
        str=br.readLine().split(" ");
        long[] a=new long[N];
        for(int i=0;i<N;i++){
        	a[i]=Integer.parseInt(str[i]);
        }
        Arrays.sort(a);
        for(int i=1;i<M;i++){
        	System.out.print(a[N-i]+" ");
        }
        System.out.println(a[N-M]);
	}

}

7-3 抢红包 (25分)

没有人没抢过红包吧…… 这里给出N个人之间互相发红包、抢红包的记录，请你统计一下他们抢红包的收获。

输入格式：

输入第一行给出一个正整数N（≤10​4​​），即参与发红包和抢红包的总人数，则这些人从1到N编号。随后N行，第i行给出编号为i的人发红包的记录，格式如下：

KN​1​​P​1​​⋯N​K​​P​K​​

其中K（0≤K≤20）是发出去的红包个数，N​i​​是抢到红包的人的编号，P​i​​（>0）是其抢到的红包金额（以分为单位）。注意：对于同一个人发出的红包，每人最多只能抢1次，不能重复抢。

输出格式：

按照收入金额从高到低的递减顺序输出每个人的编号和收入金额（以元为单位，输出小数点后2位）。每个人的信息占一行，两数字间有1个空格。如果收入金额有并列，则按抢到红包的个数递减输出；如果还有并列，则按个人编号递增输出。

输入样例：

10
3 2 22 10 58 8 125
5 1 345 3 211 5 233 7 13 8 101
1 7 8800
2 1 1000 2 1000
2 4 250 10 320
6 5 11 9 22 8 33 7 44 10 55 4 2
1 3 8800
2 1 23 2 123
1 8 250
4 2 121 4 516 7 112 9 10

输出样例：

1 11.63
2 3.63
8 3.63
3 2.11
7 1.69
6 -1.67
9 -2.18
10 -3.26
5 -3.26
4 -12.32

 思路：

题目的主要难点在于各种情况的排序，所以自己建一个类存放各种属性并继承Comparable接口，再利用Arrays类的sort来排序就很简单了！之前没用DecimalFormat保留两位小数，所以一直答案错误！

代码：

只对第一个点

import java.text.DecimalFormat;
import java.util.*;
public class 抢红包 {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
        Scanner in =new Scanner(System.in);
        DecimalFormat df=new DecimalFormat(".00");//保留小数点后两位
        int N=in.nextInt();
        in.nextLine();
        Person[] p=new Person[N+1];//对象数组
        for(int i=1;i<=N;i++){
        	p[i]=new Person();
        	p[i].number=i;
        }
        String str;
        for(int i=1;i<=N;i++){
        	String a[];
        	str=in.nextLine();
        	a=str.split(" ");
        	for(int j=1;j<a.length;j+=2){//每两个数据一对，个人编号
        		int n=Integer.parseInt(a[j]);//抢到红包的人的编号
        		double money=Double.parseDouble(a[j+1]);//此次抢到的红包金额
        		p[n].earn+=money;
        		p[n].redNum++;//第n个人抢到红包数加1
        		p[i].earn-=money;//发红包的人支出
        	}
        }
        for(int i=1;i<=N;i++){
        	p[i].earn/=100.0;    
        }
        Arrays.sort(p,1,N+1);
        for(int i=1;i<=N;i++){
        	System.out.println(p[i].number+" "+df.format(p[i].earn));
        }
	}

}
class Person implements Comparable<Person>{
	public double earn;
	public int redNum;
	public int number;
	@Override
	public int compareTo(Person o) {
		// TODO 自动生成的方法存根
		if(this.earn==o.earn){//若收入相等，比较收到的红包数
			if(this.redNum==o.redNum){
				if(this.number>o.number){
					return 1;
				}
				else{
					return -1;
				}
			}
			else if(this.redNum>o.redNum){
				return -1;//递减
			}
			else{
				return 1;
			}
		}
		else if(this.earn>o.earn){
			return -1;
		}
		else{
			return 1;
		}
	}
}

7-8 最长对称子串 (25分)

对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出11。

输入格式：

输入在一行中给出长度不超过1000的非空字符串。

输出格式：

在一行中输出最长对称子串的长度。

输入样例：

Is PAT&TAP symmetric?

输出样例：

11

 思路：

思路比较简单，双重循环遍历出所有字串，再根据字串的长度（偶数或奇数）来分情况讨论。注意一个字符或所有字符都不相同时的情况，应该输出1，所以j要从i开始！！！

 AC代码：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 最长对称子串 {

	public static void main(String[] args) throws IOException {
		// TODO 自动生成的方法存根
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String str=br.readLine();
        int L=str.length();//既是字符数量也是最后一个字符的坐标
        int result=0;
        for(int i=0;i<L;i++){
        	for(int j=i;j<L;j++){
        		if((j-i+1)%2==1){//奇数
        			int flag=1;
        			int count=0;
        			for(int k=i;k<(j+i)/2;k++,count++){
        				if(str.charAt(k)!=str.charAt(j-count)){
        					flag=0;
        					break;
        				}
        			}
        			if(flag==1){
        				if(result<(j-i+1)){
        					result=j-i+1;
        				}
        			}
        		}
        		else{//偶数
        			int flag=1;
        			int count=0;
        			for(int k=i;k<(j+i)/2+1;k++,count++){
        				if(str.charAt(k)!=str.charAt(j-count)){
        					flag=0;
        					break;
        				}
        			}
        			if(flag==1){
        				if(result<(j-i+1)){
        					result=j-i+1;
        				}
        			}
        		}
        	}
        }
        System.out.println(result);
	}

}