美团笔试题-最大期望分数
小美即将进行期末考试！小美现在盘算了一下，一共有n道试题，对于第 i 道试题，小美有着pi的概率做对，
获得ai的分值，另外(1-pi)的概率做错，获得0分。小美的总分即是每道题获得的分数之和。小美不甘于此！
她决定突击复习，因为时间有限，她最多复习m道试题，使得复习后的试题正确率提升到100%。小美想知道，如果她以最佳方式进行复习，能获得的期望总分最大是多少。
输入描述
第一行两个正整数n和m，表示总试题数和最多复习试题数。
接下来一行n个整数，分别为p1 p2...pn，表示小美有pi%的概率，即pi=pi/100的概率做对第i个题。（注意，这里为了简单起见，将概率pi扩张100倍成为整数pi方便输入）
接下来一行n个整数，分别表示a1 a2...an，分别表示第 i 个题做对的分值。
数字间两两有空格隔开，对于所有数据，1≤m≤n≤50000,0≤pi≤100,1≤ai≤1000
输出描述
输出一行一个恰好两位的小数，表示能获得的最大期望总分。（如果答案为10应输出10.00，2.5应输出2.50）
样例输入
2 1
89 38
445 754
样例输出
1150.05
提示
如果都不复习，小美总分的期望为89%*445+38%*754=682.57
如果复习第一道题，小美总分的期望为100%*445+38%*754=731.52
如果复习第二道题，小美总分的期望为89%*445+100%*754=1150.05
所以选择复习第二道题，这样能获得最大期望总分1150.05
#美团笔试#
获得ai的分值，另外(1-pi)的概率做错，获得0分。小美的总分即是每道题获得的分数之和。小美不甘于此！
她决定突击复习，因为时间有限，她最多复习m道试题，使得复习后的试题正确率提升到100%。小美想知道，如果她以最佳方式进行复习，能获得的期望总分最大是多少。
输入描述
第一行两个正整数n和m，表示总试题数和最多复习试题数。
接下来一行n个整数，分别为p1 p2...pn，表示小美有pi%的概率，即pi=pi/100的概率做对第i个题。（注意，这里为了简单起见，将概率pi扩张100倍成为整数pi方便输入）
接下来一行n个整数，分别表示a1 a2...an，分别表示第 i 个题做对的分值。
数字间两两有空格隔开，对于所有数据，1≤m≤n≤50000,0≤pi≤100,1≤ai≤1000
输出描述
输出一行一个恰好两位的小数，表示能获得的最大期望总分。（如果答案为10应输出10.00，2.5应输出2.50）
样例输入
2 1
89 38
445 754
样例输出
1150.05
提示
如果都不复习，小美总分的期望为89%*445+38%*754=682.57
如果复习第一道题，小美总分的期望为100%*445+38%*754=731.52
如果复习第二道题，小美总分的期望为89%*445+100%*754=1150.05
所以选择复习第二道题，这样能获得最大期望总分1150.05
根据每题复习后的收益进行排序即可
方法1：
首先可以确定的是获得最大分数的前提是 m次复习都使用 。因为用了就是100%获得分数 ；那么我们要做的就是 找出该复习哪m门课。 使得效益最好直接的方式： 暴力法枚举法。
这里我用的是回溯法来进行暴力寻找最大期望分数，详解见代码注释
方法2：
更简单一些，直接计算出所有成绩的损失分数，复习最大的m个即可。
public class Demo2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] p =new int[n];
int[] score =new int[n];
for (int i = 0; i < n; i++) {
p[i]=sc.nextInt();
}
for (int i = 0; i < n; i++) {
score[i]=sc.nextInt();
}
boolean[] flag=new boolean[n];//用来标记哪些分数已经被复习了。这样之后求和就不用再算了
Demo2.getmaxscore(flag,p,0,score,n,m,0);
System.out.println(Demo2.max);
}
static int count=0;
static double max=0;
public static void getmaxscore(boolean[] flag,int[] p,double sum,int[] score,int n,int m,int start){//暴力出那m个数，再求一次和，更新当前最大值
if(count==m){//当找出m个数时，停止回溯，开始计算剩下的那些没复习的和，将他们相加
for (int i = 0; i < n; i++) {
if(!flag[i]){//没有复习
sum+=score[i]*p[i]*0.01;
}
}
max=Math.max(max, sum);//最后得出本次期望分数，和之前的比较，得到当前最大期望分数。然后本次递归查询结束，return后进行第二次的递归。。。重复进行 直到完毕。
return;
}
for (int i = start; i < n; i++) {//回溯法的经典for循环，枚举出m个数，start是每次的起始位置
sum+=score[i];//计算这m个数的和，乘100%，所以直接相加
flag[i]=true;//标记为已复习
count++;//count初始为0，每回溯一次就+1；
getmaxscore(flag,p,sum,score,n, m, start+1);//
sum=sum-score[i];//回溯法之撤回
flag[i]=false;//同上
count--;//同上
}
}
} 