小v今年有
门课,每门都有考试,为了拿到奖学金,小v必须让自己的平均成绩至少为
。
每门课由平时成绩和考试成绩组成,满分为
。
现在他知道每门课的平时成绩为
,若想让这门课的考试成绩多拿一分的话,小v要花
的时间复习,不复习的话当然就是0分。
同时我们显然可以发现复习得再多也不会拿到超过满分的分数。为了拿到奖学金,小v至少要花多少时间复习。
第一行三个整数,
,
。(
)
接下来行,每行两个整数
。(
)
一行输出答案。
5 10 9 0 5 9 1 8 1 0 1 9 100
43
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNextLine()) { String[] n_r_avg = sc.nextLine().split(" "); int n = Integer.valueOf(n_r_avg[0]); int r = Integer.valueOf(n_r_avg[1]); int avg = Integer.valueOf(n_r_avg[2]); int[][] a_b = new int[n][2]; for (int i = 0; i < n; i++) { for (int j = 0; j < 2; j++) { a_b[i][j] = sc.nextInt(); } sc.nextLine(); } long time = getMinScore(a_b, n, r, avg); System.out.println(time); } } public static long getMinScore(int[][] a_b, int n, int r, int avg) { long sum = 0; for (int[] p : a_b) sum += p[0]; if (sum >= n * avg) return 0; // 已经超过了需要达到的分数 n * avg,直接返回0 long leave = n * avg - sum; Arrays.sort(a_b, (o1, o2) -> Long.compare(o1[1], o2[1])); long time = 0; for (int i = 0; i < a_b.length; i++) { if (leave >= r - a_b[i][0]) { time += (r - a_b[i][0]) * a_b[i][1]; leave -= (r - a_b[i][0]); } else { time += (leave * a_b[i][1]); leave = 0; return time; // 达到需要的分数,返回对应的需要花费的时间 } } return -1; // } }
import java.util.Scanner; import java.util.*; import java.util.stream.Collectors; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static int cal(Map map, List keys, int target){ if(target <= 0){return 0;} int count = 0; for(int i = 0; i 0;i++){ //该分数的单价 int price = keys.get(i); //剩余分数数量 int value = map.get(price); // System.out.println(price + " " +value); if(value < target ){ target = target - value; count = count + value * price; continue; } //还差的就是target count = count + target*price; return count; } return count; } public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNextInt()) { // 注意 while 处理多个 case int n = in.nextInt(); int r = in.nextInt(); int avg = in.nextInt(); int tmp = avg*n; int cur = 0; Map map = new HashMap(); List keys = new ArrayList(); for(int i = 0; i < n; i++){ int had = in.nextInt(); int price = in.nextInt(); // System.out.print(had + " "); // System.out.println(price); cur = cur + had; int value = map.containsKey(price) ? map.get(price) + (r - had): r - had; map.put(price, value); if(!keys.contains(price)){ keys.add(price); } } keys = keys.stream().distinct().sorted().collect(Collectors.toList()); System.out.println(cal(map,keys, tmp - cur)); } } }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Arrays; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String line; while((line = br.readLine()) != null){ String[] params = line.split(" "); int n = Integer.parseInt(params[0]); int r = Integer.parseInt(params[1]); int avg = Integer.parseInt(params[2]); int[][] scores = new int[n][2]; int base = 0; // 平时总成绩,作为基础得分 for(int i = 0; i < n; i++){ String[] pair = br.readLine().split(" "); scores[i][0] = Integer.parseInt(pair[0]); scores[i][1] = Integer.parseInt(pair[1]); base += scores[i][0]; } Arrays.sort(scores, (a, b) -> a[1] - b[1]); // 把复习起来最轻松的排在前面 System.out.println(solve(n, r, avg, scores, base)); } } private static long solve(int n, int r, int avg, int[][] scores, int base) { long timeConsuming = 0; for(int i = 0; i < n && n*avg > base; i++){ int time = Math.min(r - scores[i][0], n*avg - base); // 课程得分不能超过满分 timeConsuming += time * scores[i][1]; base += time; } return timeConsuming; } }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); while(sc.hasNext()){ int n=sc.nextInt(); int r=sc.nextInt(); int avg=sc.nextInt(); int[][] course=new int[n][2]; PriorityQueue<int[]> queue=new PriorityQueue<int[]>(new Comparator<int[]>(){ public int compare(int[] o1,int[] o2){ return o1[1]-o2[1]; } }); long pingshifen=0; for(int i=0;i<n;i++){ int a=sc.nextInt(); int b=sc.nextInt(); course[i]=new int[]{a,b}; queue.offer(course[i]); pingshifen+=a; } long sum=n*avg-pingshifen; long time=0; while(!queue.isEmpty()&&sum>=0){ if(sum==0){ break; } int[] temp=queue.poll(); long diff=Math.min(r-temp[0],sum); time+=diff*temp[1]; sum-=diff; } System.out.println(time); } } }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); while(in.hasNextInt()){ int n = in.nextInt(); int r = in.nextInt(); int avg = in.nextInt(); long totleScore = n * avg, baseScore = 0; int[][] arr = new int[n][2]; for(int i = 0; i < n; i++){ arr[i][0] = in.nextInt(); arr[i][1] = in.nextInt(); baseScore += arr[i][0]; } long restScore = totleScore - baseScore; Arrays.sort(arr, (o1, o2)-> {return o1[1] - o2[1] == 0? o1[0] - o2[0]:o1[1] - o2[1];}); long ans = 0; for(int i = 0; i < n; i++){ while(arr[i][0] < r && restScore > 0){ arr[i][0]++; restScore--; ans += arr[i][1]; } if(restScore < 0) break; } System.out.println(ans); } } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { long n = sc.nextInt(); long r = sc.nextInt(); long avg = sc.nextInt(); long[][] arr = new long[(int) n][2]; for (int i = 0; i < n; i++) { arr[i][0] = sc.nextInt(); arr[i][1] = sc.nextInt(); } long res = result(n, r, avg, arr); System.out.println(res); } sc.close(); } public static long result(long n, long r, long avg, long[][] arr) { Arrays.sort(arr, (o1, o2) -> (int) (o1[1] - o2[1])); long res = 0;//一共需复习时间 long socre = n * avg;//n门课拿奖学金所需的分数 for (long[] num : arr) { socre -= num[0];//去除平时分,剩下的分数是复习所取得的 } for (long[] num : arr) { if (r - num[0] < socre) { res += (num[1] * (r - num[0])); socre -= r - num[0]; } else { res += ((num[1] * (socre - num[0]))); break; } } return res; } }
public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while(scanner.hasNext()) { int n, r, avg, sum = 0; n = scanner.nextInt(); r = scanner.nextInt(); avg = scanner.nextInt(); int[] a = new int[n]; int[] b = new int[n]; for (int i = 0; i < n; i++) { a[i] = scanner.nextInt(); b[i] = scanner.nextInt(); sum += a[i]; } for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1 - i; j++) { if (b[j] > b[j + 1]) { int temp = b[j]; int flag = a[j]; b[j] = b[j + 1]; a[j] = a[j + 1]; b[j + 1] = temp; a[j + 1] = flag; } } } int result = n * avg; int time = 0; int k = 0; while (sum < result) { if (sum + (r - a[k]) <= result) { time += (r - a[k])*b[k]; sum += (r - a[k]); k++; } else { time += (result - sum) * b[k]; sum = result; } } System.out.println(time); } }
import java.util.Comparator; import java.util.PriorityQueue; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int n = sc.nextInt(); int r = sc.nextInt(); int avg = sc.nextInt(); course[] c = new course[n]; for (int i = 0; i < n; i++) { int a = sc.nextInt(); int b = sc.nextInt(); c[i] = new course(a, b); } long res = solve(c, n, r, avg); System.out.println(res); } sc.close(); } private static long solve(course[] c, int n, int r, int avg) { long res = 0; PriorityQueue<course> q = new PriorityQueue<course>(new Comparator<course>() { @Override public int compare(course o1, course o2) { return o1.b - o2.b; } }); long curTotal = 0; for (course cc : c) { q.add(cc); curTotal += cc.a; } long total = avg * n; long dif = total - curTotal; if (dif <= 0) return 0; while (dif > 0) { course cur = null; if (!q.isEmpty()) { cur = q.poll(); } if (cur != null) { if (cur.a == r) continue; if (dif > (r - cur.a)) { res += (r - cur.a) * cur.b; dif -= (r - cur.a); } else { res += dif * cur.b; dif = 0; } } } return res; } public static class course { int a; int b; public course(int a, int b) { this.a = a; this.b = b; } } }
利用贪心算法就可解出来,只不过要排除加完所有基本分已经达到平均分的情况。然后数据用long保存即可。
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class WY1 { static class Obj { int a; int b; public Obj(int a, int b) { this.a = a; this.b = b; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()) { int n = sc.nextInt(); int r = sc.nextInt(); int avg = sc.nextInt(); long idealScore = n*avg; long time = 0; List list = new ArrayList(); for(int i = 0; i < n; i++) { int a = sc.nextInt(); int b = sc.nextInt(); list.add(new Obj(a, b)); idealScore -= a; } if(idealScore <= 0) { System.out.println(0); continue; } list.sort((Obj o1, Obj o2) -> o1.b - o2.b); for (Obj o:list) { if(o.a >= r) continue; if(idealScore - (r-o.a) > 0) { idealScore -= (r-o.a); time += (r-o.a)*o.b; }else { time += idealScore*o.b; break; } } System.out.println(time); } } }
import java.util.PriorityQueue; import java.util.Scanner; /** * 先把用时间少的复习到满分,再考虑时间多的,用优先级队列 */ public class Main{ static class Score implements Comparable<Score>{ public long score; public long userTime; @Override public int compareTo(Score o) { return (int)(this.userTime - o.userTime); } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNextInt()) { int n = sc.nextInt(); int maxScore = sc.nextInt(); int avg = sc.nextInt(); long sumTime = 0; long sumScore = 0; PriorityQueue<Score> priorityQueue = new PriorityQueue<Score>(); for (int i = 0; i < n; i++) { Score score = new Score(); score.score = sc.nextInt(); sumScore += score.score; score.userTime = sc.nextInt(); priorityQueue.add(score); } while (sumScore < avg * n && !priorityQueue.isEmpty()){ Score poll = priorityQueue.poll(); while (poll.score < maxScore && sumScore < avg * n){ poll.score++; sumScore++; sumTime += poll.userTime; } } System.out.println(sumTime); } } }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { int n = in.nextInt(); long r = in.nextLong(); long avg = in.nextLong(); if (n < 1 && n > Math.pow(10, 5) || r < 1 && r > Math.pow(10, 9) || avg < 1 && avg > Math.pow(10, 6)) { return; } int[] a = new int[n]; int[] b = new int[n]; long score = n * avg; for (int i = 0; i < n; i++) { a[i] = in.nextInt(); score -= a[i]; b[i] = in.nextInt(); } long ans = getResult(a,b,score,r,n); System.out.println(ans); } } private static long getResult(int[] a, int[] b, long score, long r, int n) { // TODO Auto-generated method stub long count = 0; while (score > 0) { long minTime = Integer.MAX_VALUE; int minTimeIndex = 0; for (int i = 0; i < n; i++) { if (minTime > b[i] && a[i] < r) { minTime = b[i]; minTimeIndex = i; } } while (score > 0 && a[minTimeIndex] < r) { ++a[minTimeIndex]; --score; count += b[minTimeIndex]; } } return count; } }
importjava.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = newScanner(System.in);
while(sc.hasNext()){
intnumTest;
longfScore, avg, total_need, now_score;
longscore, cost;
longmin_cost;
numTest = sc.nextInt();
fScore = sc.nextLong();
long[][] glist = newlong[numTest][2];
avg = sc.nextLong();
now_score = 0;
min_cost = 0;
total_need = (long)numTest * avg;
for(inti = 0; i<numTest; i++){
glist[i][0] = sc.nextLong();
glist[i][1] = sc.nextLong();
now_score += glist[i][0];
}
Arrays.sort(glist, newComparator<long[]>() {
@Override
publicintcompare(long[] o1, long[] o2) {
returnLong.compare(o1[1], o2[1]);
}
});
// for(int i=0; i<numTest; i++){
// if(now_score + fScore - glist[i][0] >= total_need){
// min_cost += (total_need - now_score) * glist[i][1];
// break;
// } else {
// now_score += fScore - glist[i][0];
// min_cost += (fScore - glist[i][0]) * glist[i][1];
// }
// }
for(int i=0; i<numTest && now_score < total_need; i++){
if(now_score + fScore - glist[i][0] >= total_need){
min_cost += (total_need - now_score) * glist[i][1];
now_score = total_need;
} else{
now_score += fScore - glist[i][0];
min_cost += (fScore - glist[i][0]) * glist[i][1];
}
}
System.out.println(min_cost);
}
sc.close();
}
}
//老哥们,40%是因为没有检测一开始就不用复习的,直接输出0就行。 //90%是数据范围太大了,使用long兴变量 import java.util.*; public class Main{ public static void main(String[] args){ // int a = 1240 * 85; // System.out.println(a); Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int n = sc.nextInt(); int r = sc.nextInt(); int avg = sc.nextInt(); long time = 0; long total = 0; List<cc> list = new ArrayList<cc>(); for(int i=0; i<n ;i++){ long ai = sc.nextLong(); total += ai; list.add(new cc(ai,sc.nextLong())); // System.out.println(i); } total = n*avg - total; if(total <=0){ System.out.println(0); continue; } Comparator<cc> c = new Comparator<cc>(){ public int compare(cc c1, cc c2){ if(c1.bi <= c2.bi){ return -1; }else{ return 1; } } }; Collections.sort(list,c); for(int i=0; i<list.size(); i++){ cc ctemp = list.get(i); if(total <=r - ctemp.ai){ time += total*ctemp.bi; break; }else{ time += (r-ctemp.ai)*ctemp.bi; total -= r-ctemp.ai; } } System.out.println(time); } } } class cc{ long ai; long bi; public cc(long ai, long bi){ this.ai = ai; this.bi = bi; } }
//说明:以下代码并没有完全通过,可以我觉得思路跟前辈的一样,不知为何,请指点 //2017-3-5 19:35 //看总分还差多少,先拿最容易得分的开始 import java.util.*; public class Main { public static void main(String[] args){ Scanner sc=new Scanner(System.in); while(sc.hasNext()){ int n=sc.nextInt(); long r=sc.nextLong(); long avg=sc.nextLong(); sc.nextLine(); long[] a=new long[n]; long[] b=new long[n]; for(int i=0;i<n;i++){ String[] s=sc.nextLine().split(" "); a[i]=Long.parseLong(s[0]); b[i]=Long.parseLong(s[1]); } //已经获得的分数即平时分 long score1 = 0; for(int i=0;i<a.length;i++){ score1+=a[i]; } //冒泡排个序 for(int i=1;i<b.length;i++){ for(int j=0;j<b.length-i;j++){//后边还有一个位置 if(b[j]>b[j+1]){ long t=b[j]; b[j]=b[j+1]; b[j+1]=t; //a也跟着一起换 long t2=a[j]; a[j]=a[j+1]; a[j+1]=t2; } } } //int totaltime=0; long totaltime=0; //算出还差的总分 long dis = avg * n - score1; if(dis>0){ for(int i=0;i<b.length;i++){ //把第i门努力到满分可以,会超分吗 if((r-a[i])<=dis){//如果加满还没有超,那么这一门就学到满分为止 dis-=(r-a[i]); totaltime+=(r-a[i])*a[i]; }else{ //差的分很少了 totaltime+=dis * a[i]; break; //这时已经满足了,剩下的课不管了 } } } System.out.println(totaltime); } } }
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { int n = sc.nextInt(); long r = sc.nextLong(); long avg = sc.nextLong(); Score[] score = new Score[n]; long PresentSum = 0; for (int i = 0; i < score.length; i ++ ) { score[i] = new Score(sc.nextLong(), sc.nextLong()); PresentSum += score[i].presentGrades; } Arrays.sort(score); // 按耗时从小到大排序 long cost = 0; long need = n * avg - PresentSum; for (Score s:score) { if(need <= 0) break; long requiredGrades = Math.min(need, r - s.presentGrades); cost += requiredGrades * s.requiredTime; need -= requiredGrades; } System.out.println(cost); } } static class Score implements Comparable<Score> { long presentGrades; long requiredTime; public Score(long now, long time) { this.presentGrades = now; this.requiredTime = time; } @Override public int compareTo(Score o) { return this.requiredTime > o.requiredTime ? 1 : - 1; } } }
import java.util.Comparator; import java.util.PriorityQueue; import java.util.Scanner; public class Main { public static class Score { int a; int b; int current; public Score(int a, int b) { this.a = a; this.b = b; this.current = a; } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); PriorityQueue<Score> priorityQueue = null; while (scanner.hasNextInt()) { int n = scanner.nextInt(); int full = scanner.nextInt(); int avg = scanner.nextInt(); int total = n * avg; priorityQueue = new PriorityQueue<Score>(n, new Comparator<Score>() { @Override public int compare(Score o1, Score o2) { if (o1.b == o2.b) return 0; else if (o1.b > o2.b) return 1; else return -1; } }); for (int i = 0; i < n; ++i) { int a = scanner.nextInt(); int b = scanner.nextInt(); total -= a; Score score = new Score(a, b); priorityQueue.add(score); } long needTime = 0; while (!priorityQueue.isEmpty() && total > 0) { Score score = priorityQueue.remove(); int tmp = full - score.a; if (total < tmp) { tmp = total; } score.current = full; total -= tmp; needTime += tmp * score.b; } System.out.println(needTime); } scanner.close(); } }