WY1. 奖学金
描述
小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） 注意：本题含有多组样例输入。输出描述
每个用例对应一行输出答案。示例1
输入:
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 解法, 执行用时: 3ms, 内存消耗: 300KB, 提交时间: 2021-10-03
#include <stdio.h>
void my_quick_sort(int *A, int *B, int left, int right)
{
if(left < right){
int record_A = A[left], record_B = B[left], i = left, j = right;
while(i < j)
{
while(i<j && B[j]>=record_B)
--j;
B[i] = B[j], A[i] = A[j];
while(i<j && B[i]<=record_B)
++i;
B[j] = B[i], A[j] = A[i];
}
B[i] = record_B, A[i] = record_A;
my_quick_sort(A, B, left, i-1);
my_quick_sort(A, B, i+1, right);
}
}
int main(void)
{
int n, r, avg;
while(scanf("%d %d %d", &n, &r, &avg) != EOF)
{
long long cnt = 0, rest = (long long)n*avg; int A[n], B[n];
for(int i=0,A_val; i<n; ++i)
{
scanf("%d %d", &A_val, B+i);
A[i] = r-A_val;
rest -= A_val;
}
if(rest > 0){
my_quick_sort(A, B, 0, n-1);
int i = 0;
while(i<n && rest>A[i])
{
cnt += (long long)A[i]*B[i];
rest -= A[ i++ ];
}
printf("%lld\n", i<n ? cnt+rest*B[i] : cnt);
}
else printf("0\n");
}
return 0;
}
C 解法, 执行用时: 3ms, 内存消耗: 332KB, 提交时间: 2021-09-23
#include<stdio.h>
typedef struct ke{
long long ketang;
long long time;
}ke;
int cmp(const void * a1,const void * a2){
ke t1=*((ke*)a1);
ke t2=*((ke*)a2);
return t1.time-t2.time;
}
int main(){
long long n,r,avg;
long long time=0;
while(scanf("%ld %ld %ld",&n,&r,&avg)!=EOF){
time=0;
long long target = n*avg;
long long now=0;
ke list[n+3];
for(int i = 0;i<n;i++){
scanf("%ld %ld",&(list[i].ketang),&(list[i].time));
now+=list[i].ketang;
}
if(now >= target){
printf("0\n");
continue;
}
qsort(list,n,sizeof(ke),cmp);
/*for(int i = 0;i<n;i++){
printf("%d %d\n",(list[i].ketang),(list[i].time));
}*/
for(int i =0;i<n;i++){
if((now+r-(list[i].ketang))<target){
time=time+(r-list[i].ketang)*(list[i].time);
now=now+(r-list[i].ketang);
}else{
time=time+((target-now)*(list[i].time));
printf("%ld\n",time);
break;
}
}
}
return 0;
}
C++ 解法, 执行用时: 3ms, 内存消耗: 376KB, 提交时间: 2020-09-05
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int n, r, avg;
typedef pair<int,int> PII;
struct Node
{
int a;
int b;
bool operator<(const Node& rhs)const
{
return b == rhs.b ? a <= rhs.a : b <= rhs.b;
}
};
int main()
{
while(scanf("%d %d %d", &n,&r,&avg) != EOF)
{
vector<pair<int, int>> v(n);
long long gotScore = 0;
long long sum = avg*n;
int s,t;
for(int i=0; i<n; ++i)
{
scanf("%d %d", &s,&t);
v[i].first = s;
v[i].second = t;
gotScore += s;
}
sort(v.begin(),v.end(),[](pair<int, int>& p1,pair<int, int>& p2){
return p1.second<p2.second;
});
long long time = 0;
for(int i=0; i<n; ++i)
{
if(gotScore >= sum) break;
if(sum-gotScore > r-v[i].first)
{
gotScore += r-v[i].first;
time += (r-v[i].first)*v[i].second;
}
else
{
time += (sum-gotScore)*v[i].second;
gotScore = sum;
}
}
printf("%lld\n", time);
}
return 0;
}
C 解法, 执行用时: 3ms, 内存消耗: 376KB, 提交时间: 2020-09-02
#include <stdio.h>
#include <stdlib.h>
long long a[100005];
long long b[100005];
void kuaisu(int head,int tail)
{
if(head>=tail)
;
else
{
int a1=head;
int a2=tail;
int a3;
int swap;
while(a1!=a2)
{
if(a1<a2&&b[a1]>b[a2])
{
swap=a[a1];
a[a1]=a[a2];
a[a2]=swap;
swap=b[a1];
b[a1]=b[a2];
b[a2]=swap;
a3=a1;
a1=a2;
a2=a3;
a2++;
}
else if(a1>a2&&b[a1]<b[a2])
{
swap=a[a1];
a[a1]=a[a2];
a[a2]=swap;
swap=b[a1];
b[a1]=b[a2];
b[a2]=swap;
a3=a1;
a1=a2;
a2=a3;
a2--;
}
else
{
if(a1>a2)
a2++;
else
a2--;
}
}
kuaisu(head,a1-1);
kuaisu(a1+1,tail);
}
}
int main()
{
long long n,r,avg;
long long i,j;
long long total=0;
long long nowgrades;
while(scanf("%lld %lld %lld",&n,&r,&avg)!=EOF)
{
for(i=1;i<=n;i++)
{
scanf("%lld %lld",&a[i],&b[i]);
}
total=n*avg;
nowgrades=0;
for(i=1;i<=n;i++)
{
nowgrades=nowgrades+a[i];
}
long long needgreades=total-nowgrades;
long long time=0;
kuaisu(1,n);
for(i=1;i<=n;i++)
{
a[i]=r-a[i];
}
total=0;
int jishuqi=0;
a[0]=0;
b[0]=0;
while(total<needgreades)
{
time=time+a[jishuqi]*b[jishuqi];
jishuqi++;
total=total+a[jishuqi];
}
total=total-a[jishuqi];
time=time+(needgreades-total)*b[jishuqi];
printf("%lld\n",time);
}
return 0;
}
C 解法, 执行用时: 3ms, 内存消耗: 376KB, 提交时间: 2020-08-22
#include <stdio.h>
#include <stdlib.h>
long long a[100005];
long long b[100005];
void kuaisu(int head,int tail)
{
if(head>=tail)
;
else
{
int a1=head;
int a2=tail;
int a3;
int swap;
while(a1!=a2)
{
if(a1<a2&&b[a1]>b[a2])
{
swap=a[a1];
a[a1]=a[a2];
a[a2]=swap;
swap=b[a1];
b[a1]=b[a2];
b[a2]=swap;
a3=a1;
a1=a2;
a2=a3;
a2++;
}
else if(a1>a2&&b[a1]<b[a2])
{
swap=a[a1];
a[a1]=a[a2];
a[a2]=swap;
swap=b[a1];
b[a1]=b[a2];
b[a2]=swap;
a3=a1;
a1=a2;
a2=a3;
a2--;
}
else
{
if(a1>a2)
a2++;
else
a2--;
}
}
kuaisu(head,a1-1);
kuaisu(a1+1,tail);
}
}
int main()
{
long long n,r,avg;
long long i,j;
long long total=0;
long long nowgrades;
while(scanf("%lld %lld %lld",&n,&r,&avg)!=EOF)
{
for(i=1;i<=n;i++)
{
scanf("%lld %lld",&a[i],&b[i]);
}
total=n*avg;
nowgrades=0;
for(i=1;i<=n;i++)
{
nowgrades=nowgrades+a[i];
}
long long needgreades=total-nowgrades;
long long time=0;
kuaisu(1,n);
for(i=1;i<=n;i++)
{
a[i]=r-a[i];
}
total=0;
int jishuqi=0;
a[0]=0;
b[0]=0;
while(total<needgreades)
{
time=time+a[jishuqi]*b[jishuqi];
jishuqi++;
total=total+a[jishuqi];
}
total=total-a[jishuqi];
time=time+(needgreades-total)*b[jishuqi];
printf("%lld\n",time);
}
return 0;
}