商人小鑫

末蓝、 2022-06-17 09:49 184阅读 0赞

###     ###

### 商人小鑫 ###

Time Limit: 1000MS  Memory Limit: 65536KB

[Submit][] [ Statistic][Statistic]

#### Problem Description ####

小鑫是个商人，当然商人最希望的就是多赚钱，小鑫也一样。   
这天，他来到了一个遥远的国度。那里有着n件商品，对于第i件商品需要付出ci的价钱才能得到。当然，对于第i件商品，小鑫在自己心中有一个估价pi：代表着当他买下这件商品后带回他的国家可以卖出的价格。小鑫只能带回m件商品，你能帮他计算一下他最多能赚多少钱么？

#### Input ####

输入有多组，到文件结束。（注：数据有很多组，请用高效率算法）

对于每一组数据。第一行是n，m。m≤n≤10000000。

紧接着有n行，每一行有两个数 c ，p。第i行代表着ci，pi。ci≤pi

数据都在int范围内 。

#### Output ####

对于每组输入数据只输出一行一个数，代表小鑫能赚多少钱。

#### Example Input ####

4 2
    1 2
    1 3
    2 2
    3 4

#### Example Output ####

#### Hint ####

#### Author ####

lin

\#include <stdio.h>  
\#include <stdlib.h>  
struct node  
\{  
    int c,p,cp;  
\} a\[100200000\],t;  
 void chosesortt(struct node a\[\],int n)  
\{  
    int i,j,k;  
    for(i=0;i<n;i++)  
    \{  
        k=i;  
        for(j=i+1;j<n;j++)  
        if((a\[j\].cp>a\[k\].cp))  
            k=j;  
        if(k!=i)  
        \{  
            t=a\[k\];  
            a\[k\]=a\[i\];  
            a\[i\]=t;  
        \}  
  
  
    \}  
  
  
\}///标记排序  
  
  
void chosesort(struct node a\[\],int left,int right)  
\{  
    int i=left,j=right,x=a\[left\].cp;  
    if(left>=right)return;  
    while(i<j)  
    \{  
        while(i<j&&a\[j\].cp<=x)j--;  
        a\[i\]=a\[j\];  
        while(i<j&&a\[i\].cp>=x)i++;  
        a\[j\]=a\[i\];  
  
  
    \}  
    a\[i\].cp=x;  
    chosesort(a,left,j-1);  
    chosesort(a,i+1,right);  
  
  
\}///标记排序  
int main()  
\{  
    int n, m;  
    while(~scanf("%d %d", &n, &m))  
    \{  
        int i;  
        for(i = 0; i < n; i++)  
        \{  
            scanf("%d %d", &a\[i\].c, &a\[i\].p);  
            a\[i\].cp = a\[i\].p - a\[i\].c;  
        \}  
        chosesortt(a,n);  
        int sum= 0;  
        for(i=0; i<m; i++)  
        \{  
            sum += a\[i\].cp;  
        \}  
        printf("%d\\n", sum);  
    \}  
    return 0;  
\}

快排与选择

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