小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();
}
}