小v今年有n门课,每门都有考试,为了拿到奖学金,小v必须让自己的平均成绩至少为avg。每门课由平时成绩和考试成绩组成,满分为r。在考试前,小v他已经知道每门课的平时成绩为ai ,假设付出的时间与获得的分数成正比,若想让这门课的考试成绩多拿一分的话,小v要花bi 的时间复习,不复习的话当然就是0分。同时我们显然可以发现复习得再多也不会拿到超过满分的分数。问小v为了拿到奖学金,至少要花多少时间复习?
第一行三个整数n,r,avg(1 <= n <= 105,1 <= r <= 109,1 <= avg <= 106),接下来n行,每行两个整数ai和bi,(0 <= ai <= 106,1 <= bi <= 106) 注意:本题含有多组样例输入。
每个用例对应一行输出答案。
5 10 9 0 5 9 1 8 1 0 1 9 100 3 5 3 2 1 4 100 3 3
43 0
示例1有两组测试用例。 对于第2组测试用例,小v的平时成绩的平均成绩为(2+4+3)/3=3分,已经达到拿奖学金的最低要求,所以可以不用复习。
/*(c/c++) 只需满足平均成绩大于等于avg即可,不管单科成绩。 所以先从花时间最少的课开始复习,使其满分。 伪码: if(当前成绩 >= avg*n) cout << 0 << endl; else{ sort(时间花费); for(时间花费从小到大) if 当前课程满分后不能获得奖学金 复习至满分,累加复习时间,然后复习下一门 else if 当前课程满分后能获得奖学金 所需时间 += (所需总分 - 当前分数)*在该课程上获得1分所需时间 输出时间; 退出循环。 } */ #include <iostream> #include <vector> #include <algorithm> using namespace std; struct score_hour { int score; int hour; }; bool cmp(score_hour a, score_hour b) { return a.hour < b.hour; } int main() { int n,r,avg; while(cin >> n >> r >> avg){ vector<score_hour> v; score_hour tmp; while(n--){ cin >> tmp.score >> tmp.hour; v.push_back(tmp); } int target = v.size()*avg; int score_cur = 0; long time = 0; for(int i=0; i<v.size(); ++i){ score_cur += v[i].score; } if(score_cur>=target) cout << 0 << endl; else{ sort(v.begin(),v.end(),cmp); for(int i=0; i<v.size(); ++i){ //该课程如果获得满分,求当前总分数 score_cur += (r - v[i].score); if(score_cur >= target){ //当前分数超过目标成绩说明该课程不得满分也可满足奖学金条件 score_cur -= (r - v[i].score); time += (target - score_cur)*v[i].hour; cout << time << endl; break; } else{ time += (r - v[i].score)*v[i].hour; } } } } return 0; }
//老哥们,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; } }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) {//注意while处理多个case int n = in.nextInt(); long r = in.nextLong(); long avg = in.nextLong(); long[][] arr = new long[n][2]; long total = avg*n;//需要的分数 long score = 0;//现在的分数 for(int i = 0;i<n;i++){ arr[i][0] = in.nextLong();//平时成绩 arr[i][1] = in.nextLong();//时间 score += arr[i][0]; } sort(arr); long time = 0; int i = 0; while(score<total&&i<n){ if(arr[i][0]<r){ //第i门课没有满分 time += arr[i][1]; score++; arr[i][0] += 1; }else{ i++; } } System.out.println(time); } in.close(); } //对时间进行排序 public static void sort(long[][]a){ for(int i = 0;i<a.length-1;i++){ boolean flag = true; for(int j = 0;j<a.length-1-i;j++){ if(a[j][1]>a[j+1][1]){ long temp = a[j][0]; long temp2 = a[j][1]; a[j][0] = a[j+1][0]; a[j+1][0] = temp; a[j][1] = a[j+1][1]; a[j+1][1] = temp2; flag = false; } } if(flag) return; } } }
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(); } }
import java.util.*; import java.util.stream.*; public class Main { public static void main(String[] args) throws Exception { Scanner scan = new Scanner(System.in); // 科目数量 int count = scan.nextInt(); // 满分 int full = scan.nextInt(); // 平均分 int avg = scan.nextInt(); List<AB> list = new ArrayList<>(); while(list.size() != count) { int a = scan.nextInt(); int b = scan.nextInt(); list.add(new AB(a, b)); } scan.close(); System.out.print(time(count, full, avg, list)); } public static long time(int count, int full, int avg, List<AB> list) { // 按b排序 List<AB> list2 = list.stream().sorted(Comparator.comparing(AB::getB)).collect(Collectors.toList()); // 总缺的分数 int less = (avg * count) - list2.stream().map(AB::getA).reduce(0, Integer::sum); // 总复习时间 long time = 0; for (AB ab : list2) { // 本门课离满分的数 int lessScore = full - ab.getA(); // 如果分数不够,继续复习 if (lessScore < less) { time += lessScore * ab.getB(); less -= lessScore; } // 如果学完这门课就够了,学够时间停止复习 else { time += less * ab.getB(); break; } } return time; } static class AB { private Integer a; private Integer b; public AB(int a, int b) { this.a = a; this.b = b; } public Integer getA() { return a; } public Integer getB() { return b; } } }
//直接使用贪心算法,对容器vector按提高一分所花费的时间从小到大排序,然后将 //花费少的先学到满分,判断当前总分是否满足平均分要求,满足要则计算学到目标 //分花费的时间;如果还不够,则继续学习下一门课程。 //注意:此题的测试用例采用了循环输入测试,所以要采用while循环!!!之前没采 //用while循环,一直通不过,弄了大半天找原因!!!
#include<iostream> #include<vector> #include<algorithm> using namespace std; bool cmp(const pair<int, int> &a, const pair<int, int> &b){ return a.second < b.second; } int main(){ int n, r, avg; while (cin >> n >> r >> avg){ vector<pair<int, int>> vec; for (int i = 0; i<n; i++){ int x, y; cin >> x >> y; vec.push_back({ x, y }); } int sum = 0; int target = n*avg; //求当前的总分 for (auto i : vec){ sum += i.first; } long time = 0; if (sum >= target){ cout << time << endl; } else{ sort(vec.begin(), vec.end(), cmp); for (int i = 0; i < n; i++){ int temp = r - vec[i].first; //当前课程学到满分,是否满足目标分数要求 if (sum + temp >= target){ //满足 time += (target - sum)*vec[i].second; sum = target; break; } else{ //不满足 sum += temp; time += temp*vec[i].second; } } cout << time << endl; } } return 0; }
#include<iostream> #include<vector> #include<algorithm> using namespace std; struct score_hour { int score; int hour; score_hour(int ai, int bi){ score = ai; hour = bi; } }; // for sort bool cmp(score_hour a, score_hour b) { return a.hour < b.hour; } int main(){ // for store ai and bi vector<score_hour> vec; // for store input int n, r, avg; cin >> n >> r >> avg; // store input ai and bi for (int i = 0; i < n; i++){ int ai, bi; cin >> ai >> bi; score_hour* tmp = new score_hour(ai, bi); vec.push_back(*tmp); } // for debug // cout << vec[0].score << vec[0].hour << endl; sort(vec.begin(), vec.end(), cmp); // need scores int need_points = 0; for (int i = 0; i < vec.size(); i++) { need_points += (avg - vec[i].score); } //std:: cout << "need_pints:" << need_points << endl; // at least need review hours int need_hours = 0; for (int i = 0; i < vec.size() && need_points > 0; i++){ if (vec[i].score < r){ int tmp = r - vec[i].score; if (tmp > need_points){ need_hours += need_points*vec[i].hour; need_points = 0; } else{ need_hours += tmp * vec[i].hour; // std::cout << "need_ hours:" << need_hours << endl; need_points -= tmp; } } // std:: cout << "need_pints:" << need_points << endl; } std::cout << need_hours << endl; // std::system("pause"); return 0; }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner scan = new Scanner(System.in); while(scan.hasNext()){ int n = scan.nextInt(); int r = scan.nextInt(); int avg = scan.nextInt(); List<Course> list = new ArrayList<Course>(n); int score = 0; int a,b; for(int i=0; i<n; i++){ a = scan.nextInt(); b = scan.nextInt(); score += a; list.add(new Course(a, b)); } Collections.sort(list); int i=0, j=0;////i 表示复习得分 int needScore = avg*n-score; long time = 0; while(i < needScore){ while(i<needScore && list.get(j).grade < r){ time += list.get(j).time; list.get(j).grade++; i++; } if(i < needScore) j++; } System.out.println(time); } } } class Course implements Comparable<Course>{ int grade; int time; public Course(int grade, int time){ this.grade = grade; this.time = time; } public int compareTo(Course arg){ return this.time-arg.time; } }
#include<iostream> #include<vector> #include<algorithm> using namespace std; struct Ai_bi{ int ai; int bi; }; bool compare(Ai_bi a1, Ai_bi a2) { return a1.bi < a2.bi; } int main() { int n, r, avg; while (cin >> n >> r >> avg) { vector<Ai_bi> ab(n); for (int i = 0; i < n; i++) cin >> ab[i].ai >> ab[i].bi; int targ = n*avg; int temp = 0; for (auto i : ab) temp += i.ai; temp = targ - temp;//还需要多少分 long time = 0; sort(ab.begin(), ab.end(), compare); for (int i = 0; temp>0&&i < n;i++) { int res = r - ab[i].ai; if (res < temp) { temp -= res; time += ab[i].bi*res; } else { time += ab[i].bi*temp; temp = 0; break; } } if (temp>0) cout << "error!" << endl; else cout << time << endl; } return 0; }
// 大致思路就是先复习花费代价最小的课程,因此需要根据bi对其进行一个升序排序 // 然后计算所有课程达到平均分的情况下,还需要在平时成绩的基础上得到多少分 // 最后根据这个需要得到的分数 needed去将队列中的课程按代价递增的顺序依次修到满分,直到修够needed分 import java.util.ArrayList; import java.util.Collections; import java.util.List; public class Main { public static void main(String[] args) { java.util.Scanner cin = new java.util.Scanner(System.in); while(cin.hasNext()){ int n, r, avg; n = cin.nextInt(); r = cin.nextInt(); avg = cin.nextInt(); List<Pair> scoreQueue = new ArrayList<Pair>(); int needed = 0; int aSum = 0; int a = 0, b = 0; for(int i=0; i<n; i++){ a = cin.nextInt(); aSum += a; b = cin.nextInt(); scoreQueue.add(new Pair(a, b)); } needed = n * avg - aSum; //cin.close(); // System.out.println(needed); Collections.sort(scoreQueue); long timeSum = 0; int getted = 0; for(int i=0; i<scoreQueue.size(); i++){ if((getted + r - scoreQueue.get(i).a) < needed){ timeSum += (r - scoreQueue.get(i).a) * scoreQueue.get(i).b; getted += (r - scoreQueue.get(i).a); }else{ if(getted < needed){ timeSum += (needed - getted) * scoreQueue.get(i).b; break; } } } System.out.println(timeSum); } cin.close(); } static class Pair implements Comparable<Pair>{ int a; int b; public Pair(int a, int b){ this.a = a; this.b = b; } @Override public int compareTo(Pair o) { if(this.b > o.b) return 1; if(this.b < o.b) return -1; return 0; } } }
import java.util.Map; import java.util.Scanner; import java.util.Set; import java.util.TreeMap; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); int n=in.nextInt(); int r=in.nextInt(); int avg=in.nextInt(); int a=0,b=0; Map<Integer,Integer> map=new TreeMap<Integer,Integer>(); int pin=0;//平时总成绩 for(int i=0;i<n;i++){ a=in.nextInt(); pin+=a; b=in.nextInt(); if(map.get(b)!=null){ map.put(b,map.get(b)+r-a); }else{ map.put(b,r-a); } } int sum=avg*n;//要拿奖学金成绩 int xu=sum-pin;//需要的考试成绩 Set<Integer> set=map.keySet(); int res=0;//记录结果 int index=0; for(Integer e:set){ index=map.get(e); if(index<=xu){ res+=index*e; xu-=index; }else{ res+=e*xu; break; } } System.out.println(res); in.close(); } }
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; } }
while True: try: x = list(map(int, input().strip().split())) l = [[0]*2 for i in range(x[0])] for i in range(x[0]): tmp = list(map(int, input().strip().split())) l[i][0], l[i][1] = tmp[0], tmp[1] l = sorted(l,key=lambda x:x[1]) total = x[0] * x[2] count, richang = 0, 0 # 处理初始的日常分 for i in range(x[0]): richang += l[i][0] if total <= richang: print(0) continue total -= richang i = 0 while i < x[0]: if x[1] - l[i][0] <= total: total -= x[1]-l[i][0] count += (x[1] - l[i][0] )* l[i][1] i += 1 continue else: count += total *l[i][1] break print(count) except: break
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); } } }
//简单贪心,优先成本低的加分 #include <iostream> #include <algorithm> using namespace std; const int N = 1e5 + 5; using ll = long long; pair<int, int> a[N]; int main() { int n, r, arg; while (cin >> n >> r >> arg) { ll target = arg * n; for (int i = 0; i < n; ++i) { cin >> a[i].second >> a[i].first; target -= a[i].second; } if (target <= 0) { cout << 0 << endl; continue; } ll ans = 0; sort(a, a + n); for (int i = 0; i < n && target > 0; ++i) { if (target >= r - a[i].second) { ans += (ll)(r - a[i].second) * (ll)a[i].first; } else { ans += (target * a[i].first); } target -= (r - a[i].second); } cout << ans << endl; } return 0; }
const readline = require('readline'), rl = readline.createInterface(process.stdin, process.stdout); let n, r, avg, arr = [], count = 0; rl.on('line', function(line) { if (n == undefined) { [n, r, avg] = line.trim().split(' '); n = +n, r = +r, avg = +avg; count = n, arr = []; } else { if (count > 0) { let temp = line.trim().split(' ') arr.push([+temp[0], +temp[1]]); count--; } if(count == 0) { let res = fun(n, r, avg, arr) console.log(res); n = undefined; } } }) var fun = function(n, r, avg, arr) { let need = n * avg, time = [], res = 0; for (let i = 0; i < n; i++) { need -= arr[i][0]; time.push([r-arr[i][0], arr[i][1]]); } if (need <= 0) return 0; time.sort((a, b)=>(a[1] - b[1])); // console.log(need, time) for (let i = 0; i < n; i++) { if (time[i][0] < need) { res += time[i][1]*time[i][0]; need -= time[i][0]; } else { res += time[i][1] * need; break; } } return res; }贪心算法,总选择最小代价得的分数。先写好输入输出流(太蹩脚了),注意无需复习的情况。
利用贪心算法就可解出来,只不过要排除加完所有基本分已经达到平均分的情况。然后数据用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); } } }
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int nCount, nMax, nAve; while (cin >> nCount >> nMax >> nAve) { vector<pair<int, int>> vecData(nCount); int nRest = nCount * nAve; long nTime = 0; for (int i = 0; i < nCount; ++i) { cin >> vecData[i].second >> vecData[i].first; nRest -= vecData[i].second; } sort(vecData.begin(), vecData.end()); auto iter = vecData.begin(); while (nRest > 0 && iter != vecData.end()) { nTime += ((nMax - iter->second) * iter->first); nRest -= (nMax - iter->second); if (nRest < 0) nTime -= (-nRest) * iter->first; ++iter; } cout << nTime << endl; } }
import java.util.*; class Course{ int ai; int bi; int remainScore; } 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(); ArrayList<Course> arrayList=new ArrayList<Course>(); int totalScore=0; for(int i=0;i<n;i++){ Course course=new Course(); course.ai=sc.nextInt(); course.bi=sc.nextInt(); course.remainScore=r-course.ai; arrayList.add(course); totalScore+=course.ai; } Collections.sort(arrayList,new Comparator<Course>(){ public int compare(Course course1,Course course2){ if(course1.bi>course2.bi) return 1; else if(course1.bi<course2.bi) return -1; return 0; } }); int reachScore=avg*n; if(totalScore>reachScore){ System.out.println(0); continue; } double result=0; for(int i=0;i<n;i++){ if(reachScore-totalScore>arrayList.get(i).remainScore){ result+=arrayList.get(i).remainScore*arrayList.get(i).bi; totalScore+=arrayList.get(i).remainScore; }else{ result+=(reachScore-totalScore)*arrayList.get(i).bi; break; } } System.out.printf("%.0f",result); System.out.println(); } } }