链家2018校园招聘秋招10月11号编程题
第一题：魔法学院
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
/**
* Created by tzy on 2017/10/11.
*/
public class Main {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
while (scanner.hasNext()){
int n=scanner.nextInt();
int max=scanner.nextInt();
int avg=scanner.nextInt();
int mincheng=avg*n;
ArrayList<KenZhu> arrayList=new ArrayList<>();
int courent=0;
for (int i = 0; i <n ; i++) {
int fen=scanner.nextInt();
int zhu=scanner.nextInt();
courent+=fen;
arrayList.add(new KenZhu(fen,zhu));
}
System.out.println(getminzhufu(arrayList,mincheng,courent,max));
}
}
private static int getminzhufu(ArrayList<KenZhu> arrayList,int minvheng,int courent,int max){
if (courent>=minvheng)
return 0;
int chazhi=minvheng-courent;
int zhufu=0;
//2个属性排序。
Collections.sort(arrayList, new Comparator<KenZhu>() {
@Override
public int compare(KenZhu o1, KenZhu o2) {
if (o1.getZhufu()>o2.getZhufu())
return 1;
else if (o1.getZhufu()<o2.getZhufu())
return -1;
else
return Integer.compare(o1.getFen(),o2.getFen());
}
});
for (KenZhu k:arrayList) {
if (chazhi==0)
break;
int cabe=max-k.getFen();
if (cabe<chazhi){
zhufu=cabe*k.getZhufu();
chazhi-=cabe;
}else {
zhufu+=chazhi*k.getZhufu();
chazhi=0;
}
}
return zhufu;
}
static class KenZhu{
private int fen;
private int zhufu;
public KenZhu(int fen, int zhufu) {
this.fen = fen;
this.zhufu = zhufu;
}
public int getFen() {
return fen;
}
public int getZhufu() {
return zhufu;
}
}
} 第二题： 小朋友有n个玩具和m条绳子，每条绳子连着两个玩具，每两个玩具之间最多连一条绳子。小朋友要取某个玩具，就要消耗能量，这个能量就是跟这个玩具直接相连的其他玩具的能量值（已经被取走的玩具就不算相连了）。如下面样例1,4个玩具和3条绳子，每个玩具的能量值分别为10,20,30,40，其中1和4相连，1和2相连，2和3相连。小朋友如果要取光所有玩具，可以先取玩具3，这样就要消耗跟3直接相连的2的能量，花费20能量；然后取玩具2，这样就要消耗玩具1的能量值，花费10能量；然后取玩具4，也花费10；最后取玩具1，因为没有玩具与之相连了，不用花费能量。所以总共需要花费20+10+10+0能量，这也是取走所有玩具花费的最少能量。
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
/**
* Created by tzy on 2017/10/11.
*没有提交不知道是否AC。但是和其他AC的代码比较了很多个测试用例，结果一样。
*贪心思想：每次取能量最大的那个礼物，和他相连的礼物能量和是所花费的代价（题目没说清楚）。
*写成了3层循环，求简化。不胜感激
*/
public class Main {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
while (scanner.hasNext()){
int n=scanner.nextInt();
int m=scanner.nextInt();
ArrayList<WanCast> arrayList=new ArrayList<>();
ArrayList<ArrayList<WanCast>> arrayLists=new ArrayList<>();
for (int i = 0; i <n ; i++) {
arrayList.add(new WanCast(i+1,scanner.nextInt()));
arrayLists.add(new ArrayList<>());
}
for (int i = 0; i <m ; i++) {
int index0=scanner.nextInt();
int index1=scanner.nextInt();
arrayLists.get(index0-1).add(arrayList.get(index1-1));
arrayLists.get(index1-1).add(arrayList.get(index0-1));
}
System.out.println(getMinEnergy(arrayList,arrayLists));
}
}
private static int getMinEnergy(ArrayList<WanCast> list,ArrayList<ArrayList<WanCast>> arrayLists){
Collections.sort(list, new Comparator<WanCast>() {
@Override
public int compare(WanCast o1, WanCast o2) {
return Integer.compare(o1.getEnergy(),o2.getEnergy());
}
});
int minEnergy=0;
//3层for循环？？
for (int i = list.size()-1; i >=0 ; i--) {
WanCast wanCast=list.get(i);
ArrayList<WanCast>temp=arrayLists.get(wanCast.getIndex()-1);
for (WanCast w:temp) {
minEnergy+=w.getEnergy();
ArrayList<WanCast> shan=arrayLists.get(w.getIndex()-1);
for (int j = 0; j <shan.size() ; j++) {
if (shan.get(j).getIndex()==wanCast.getIndex()){
shan.remove(j);
break;
}
}
}
}
return minEnergy;
}
static class WanCast{
private int index;
private int energy;
public WanCast(int index, int energy) {
this.index = index;
this.energy = energy;
}
public int getIndex() {
return index;
}
public int getEnergy() {
return energy;
}
}
}
AC代码：遍历绳子区绳子两头的最小的能量相加。居然可以AC。不解。
import java.util.Scanner;
/**
* Created by tzy on 2017/10/11.
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n= sc.nextInt();//玩具
int m =sc.nextInt();//绳子
int ae[]=new int[n];
for(int i=0;i<n;i++) {
ae[i] = sc.nextInt();
}
int la[][] = new int[m][2];
for(int i=0;i<m;i++) {
for(int j=0;j<2;j++) {
la[i][j] = sc.nextInt();
}
}
System.out.println(f(m,n,ae,la));
}
private static int f(int m,int n, int ae[],int la[][]) {
int s=0;
for(int i=0;i<m;i++) {
int a = la[i][0];
int b = la[i][1];
if(ae[a-1]>ae[b-1])
s+=ae[b-1];
else
s+=ae[a-1];
}
return s;
}
}
第三题：音乐列表，链家之前就考过，又出一边。网上的代码，改成java也没看明白。求解释
import java.util.Scanner;
/**
* Created by tzy on 2017/10/11.
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()){
n=scanner.nextInt();
m=scanner.nextInt();
p=scanner.nextInt();
for (int i=0;i<=p;i++)
for (int j=0;j<=n;j++)
dp[i][j]=-1;
System.out.println(dfs(0,0));
}
}
static long dp[][] = new long[105][105];
static int n,m,p;
static int mo = 1000000007;
public static long dfs(int i,int j){
if(dp[i][j] != -1)
return dp[i][j];
if(i==p){
if(j==n){
dp[i][j]=1;
return 1;
}else{
dp[i][j]=0;
return 0;
}
}
dp[i][j]=0;
if(j>m)
dp[i][j] = dfs(i+1,j)*(j-m);
if(j<n)
dp[i][j] += dfs(i+1,j+1)*(n-j);
if(dp[i][j]>=mo)
dp[i][j] %= mo;
return dp[i][j];
}
}
#Java工程师#
