商人小鑫 - 武林网

商人小鑫

2019-11-10 21:47:20

字体：大中小

来源：转载

供稿：网友

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 21 21 32 23 4Example Output
3Hint
 Author
lin
快速排序。。。。
01 #include<stdio.h>
02 void dog(int a[], int l, int r);
03 int main()
04 {
05     int i, n, b, c, num, m, a[100000];
06     while(scanf("%d%d", &n, &m) != EOF)
07     {
08         for(i = 0; i < n; i++)
09         {
10             scanf("%d%d", &b, &c);
11             a[i] = c - b;
12         }
13         dog(a, 0, n - 1);
14         i = n - 1;
15         num = 0;
16         while(m >  0)
17         {
18             num += a[i];
19             i--;
20             m--;
21         }
22         printf("%d/n", num);
23     }
24     return 0;
25 }
26 void dog(int a[], int l, int r)
27 {
28     if(l < r)
29     {
30         int i = l, j = r, x = a[l];
31         while(i < j)
32         {
33             while(i < j && a[j] >= x)
34                 j--;
35             if(i < j)
36                 a[i++] = a[j];
37             while(i < j && a[i] < x)
38                 i++;
39             if(i < j)
40                 a[j--] = a[i];
41         }
42         a[i] = x;
43         dog(a, l, i - 1);
44         dog(a, i + 1, r);
45     }
46     else return;
47 }