概述
问题描述
小v今年有n门课(编号为0~n-1),每门课都有考试。为了拿到奖学金,小v必须满足所有课程平均成绩至少为avg。每门课由平时成绩和考试成绩相加得到,满足为r。现知道每门课平均成绩ai(0<=i<=n-1),若想让这门课多考一分,小v需要花bi的时间复习,如果不复习,当然就是0。同时,也可能发现复习再多也不会超过满分的分数。为了拿到奖学金,小v至少需要花多少时间??
输入描述
每个测试用例第一行为整数n(1<=n<=200),表示课程数,接下来n行,每行两个整数,分别表示一门课的平均成绩ai和bi,最后一行输入满分r和希望到达的平均成绩avg,以输入n==0结束
输出描述
每个测试用例输出一行,表示小v要花的最少复习时间。
输入样例
4
80 5
70 2
90 3
60 1
100 92.5
0
输出样例
100
算法思路
这道题思路很简单,因为提高一分所需要的时间不同,只要把提高分数快的科目提高到满分,然后在进行提高次快的科目。当总科目平均分到达目标平均分就截止。难点在于,如何去存储输入数据。
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
//根据pair里面的second进行排序
bool cmp2(pair<int, int>a, pair<int, int>b)
{
return a.second < b.second;
}
//计算vector里面的平均分数
double avgS(vector<pair<int,int>> vp, int n)
{
double avgScore = 0;
vector< pair <int, int > >::iterator it;
for (it = vp.begin(); it != vp.end(); ++it)
{
avgScore += it->first;
}
return avgScore / n;
}
int main()
{
int num = 0;
while( (cin >> num) && num != 0)
{
pair<int, int> p;
typedef vector<pair<int, int>> VP;
VP vp;
for (int i = 0; i < num;++i)
{
cin >> p.first;
cin >> p.second;
vp.push_back(make_pair(p.first, p.second));//存入当前课程平均成绩以及提高一份所需要的时间
}
int hightScore = 0;
double avg = 0;
cin >> hightScore;
cin >> avg;
sort(vp.begin(), vp.end(), cmp2); //根据平均时间升序排序
int time = 0;
VP::iterator it;
for (it = vp.begin(); it != vp.end();it++)
{
while(it -> first != hightScore)
{
it -> first++;
time += it->second;
if(avgS(vp , num) >= avg)
{
break; //跳出while循环
}
}
if(avgS(vp,num) >= avg)
{
break;
}
}
cout << time << endl;
}
return 0;
}
然后仔细想想可以优化下中间没加一分又要重新计算分数平均分,让时间复杂度更小
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
//根据pair里面的second进行排序
bool cmp2(pair<int, int>a, pair<int, int>b)
{
return a.second < b.second;
}
//计算vector里面的平均分数
double avgS(vector<pair<int,int>> vp, int n)
{
double avgScore = 0;
vector< pair <int, int > >::iterator it;
for (it = vp.begin(); it != vp.end(); ++it)
{
avgScore += it->first;
}
return avgScore / n;
}
int main()
{
int num = 0;
while( (cin >> num) && num != 0)
{
// if(num ==0)
// {
// break;
// }
pair<int, int> p;
typedef vector<pair<int, int>> VP;
VP vp;
double avgScore = 0;
for (int i = 0; i < num;++i)
{
cin >> p.first;
cin >> p.second;
avgScore += p.first;
vp.push_back(make_pair(p.first, p.second));//存入当前课程平均成绩以及提高一份所需要的时间
}
int hightScore = 0;
double avg = 0;
cin >> hightScore;
cin >> avg;
sort(vp.begin(), vp.end(), cmp2); //根据平均时间升序排序
int time = 0;
VP::iterator it;
for (it = vp.begin(); it != vp.end();it++)
{
while(it -> first != hightScore)
{
it -> first++;
time += it->second;
avgScore++;
if((avgScore/num) >= avg)//更新
{
break; //跳出while循环
}
}
if(avgS(vp,num) >= avg)
{
break;
}
}
cout << time << endl;
}
return 0;
}
参考资料
https://www.bbsmax.com/A/amd08EoDdg/
https://blog.csdn.net/sinat_35121480/article/details/54728594
最后
以上就是粗犷魔镜为你收集整理的小v拿奖学金 C++实现的全部内容,希望文章能够帮你解决小v拿奖学金 C++实现所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复