我是靠谱客的博主 粗犷魔镜,最近开发中收集的这篇文章主要介绍小v拿奖学金 C++实现,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

问题描述

小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++实现所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(60)

评论列表共有 0 条评论

立即
投稿
返回
顶部