C语言贪心懒虫小鑫

ゝ一纸荒年。 2022-06-01 09:26 183阅读 0赞

### 懒虫小鑫 ###

Time Limit: 1000MS Memory Limit: 65536KB

[Submit][] [Statistic][]

#### Problem Description ####

小鑫是个大懒虫，但是这一天妈妈要小鑫去山上搬些矿石去城里卖以补贴家用。小鑫十分的不开心。不开心归不开心，小鑫还是要做这件事情的。

我们把这个事情简化一下。有n块矿石，设第i块矿石由两个数字wi和pi表示。分别表示这块石头的重量和可以卖的价钱。小鑫每次只能搬一块矿石去城里卖，所以他决定每次都会搬重量最小的那块。如果恰好有几块重量相等，那就在这几块中挑选价值最高的带走。

由于路程原因。小鑫每天只能打m个来回，也就意味着他只能卖掉m块矿石。你能计算出他能得到多少钱么？

#### Input ####

输入数据有多组，到文件结束。

对于每一组数据，第一行为n，m。m≤n≤10000。

接下来有n行，每行两个数代表石头的w与p。

#### Output ####

对于每组数据，输出有一行为一个数，为答案。

#### Example Input ####

4 2
    1 2
    1 3
    2 2
    3 4

#### Example Output ####

#include <stdio.h>
    void struff(int s[], int l, int r, int s2[])
    {
        int key1, i, j, key2;
        i = l;
        j = r;
        key1 = s[l];
        key2 = s2[l];
        if(l >= r)
            return;
        if(l < r)
        {
            while(i < j)
            {
                while(i < j && s[j] > key1)
                    j--;
                while(i < j && s[j] == key1)
                {
                    if(s2[j] > key2)
                        break;
                    else
                        j--;
                }
                s[i] = s[j];
                s2[i] = s2[j];
                while(i < j && s[i] < key1)
                    i++;
                while(i < j && s[i] == key1)
                {
                    if(s2[i] > key2)
                        i++;
                    else
                        break;
                }
                s[j] = s[i];
                s2[j] = s2[i];
            }
            s[i] = key1;
            s2[i] = key2;
            struff(s, l, i - 1, s2);
            struff(s, i + 1, r, s2);
        }
    }
    int main()
    {
        int n, m;
        while(scanf("%d %d",&n, &m) != EOF)
        {
            int s1[10010];
            int s2[10010];
            int i, money = 0;
            for(i = 0; i < n; i++)
            {
                scanf("%d%d", &s1[i], &s2[i]);
            }
            struff(s1, 0, n - 1, s2);
            i = 0;
            while(m-- && i < n)
            {
                money = money + s2[i];
                i++;
            }
            printf("%d\n", money);
        }
        return 0;
    }

[Submit]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestsubmit/cid/2382/pid/2851.html
[Statistic]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/conteststatus/cid/2382/pid/2851.html