C语言 练习题 求指正 《爱与演唱会！全明星！》

Question

Description

唐可可是《爱与演唱会》的忠实粉丝，因此她也酷爱一款名为《爱与演唱会！学园偶像祭！全明星！》的音乐游戏。然而，由于学习算法的时候过于投入，她直到游戏活动截止的前夕才突然回忆起来活动还没肝！

这款游戏游戏总共有n首乐曲，在活动期间，游玩第i首乐曲将会消耗w_i的体力并在游玩后获得v_i的活动代币(1 ≤ i ≤ n)。由于每首乐曲的游玩时间都是差不多的，因此经过唐可可的计算，在活动结束前她还可以游玩k首乐曲。

此外，唐可可不喜欢反复游玩同一首歌，因为她觉得这样坐牢会失去玩游戏带来的轻松和愉悦，这样是不会给大家带来笑容的！因此她要求这k首歌互不相同。换句话来说，每首歌她只会游玩一次。

你能帮唐可可计算出，在拿到的活动代币尽可能多的前提下消耗体力最少的方案吗？

Input
输入有n +1行。

第一行有两个整数n，k，(1 ≤ k ≤ n ≤ 10^5)分别代表游戏的乐曲总数和唐可可能游玩的乐曲数量。

接下来有n行，第i +1行有两个整数w_i​，v_i​，(0 ≤ w_i​, v_i ≤ 10^9)分别代表游玩第i首乐曲将会消耗的体力和游玩后获得的活动代币数量。

Output
输出有一行。
Sample Input 1

5 3
1 1
2 2
3 3
4 4
5 5
Sample Output 1

12 12

#include<stdio.h>
struct gequ
{
    int tili;
    int daibi;
};        //结构体
int main()
{
    int n,k;
    scanf("%d %d",&n,&k);
    struct gequ gq[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d %d",&gq[i].tili,&gq[i].daibi);
    }
    struct gequ t;
    for(int k=0;k<n;k++)  //冒泡排序
    {
        for(int i=0;i<n-1;i++)
        {
            if(gq[i].daibi<gq[i+1].daibi)
            {
                t=gq[i];
                gq[i]=gq[i+1];
                gq[i+1]=t;
            }
            else if(gq[i].daibi==gq[i+1].daibi)
            {
                if(gq[i].tili>gq[i+1].tili)
                {
                    t=gq[i];
                    gq[i]=gq[i+1];
                    gq[i+1]=t;
                }
            }
        }
    }
    int w=0,v=0;   //累加
    for(int j=0;j<k;j++)
    {
        w+=gq[j].tili;
        v+=gq[j].daibi;
    }
    printf("%d %d",v,w);
    return 0;
}

Answer 1

1. 数值范围问题，w_i, v_i达到10^9量级，k达到10^5量级，累加计算时用int类型结果会溢出的，所以你应该选用long long类型。
2. 你的冒泡排序算法写错了，即使你写对了，如果测试数据量n比较大，你的算法就会超时。比如说n是10^5量级，而k的数目很小（比如1，2，或3），你还会用冒泡排序吗？你可以考虑用一个大小为k的优先队列（v_i降序排列，如果v_i相等，按w_i升序排列）来跟踪满足要求的前k首乐曲，遍历一遍所有乐曲，依次插入队列，如果队列大小超过k，末尾元素出列。