7-9 sdut-C语言实验-商人小鑫
分数 20
全屏浏览
切换布局
作者 马新娟
单位 山东理工大学
小鑫是个商人，当然商人最希望的就是多赚钱，小鑫也一样。
这天，他来到了一个遥远的国度。那里有着n件商品，对于第i件商品需要付出ci的价钱才能得到。当然，对于第i件商品，小鑫在自己心中有一个估价pi：代表着当他买下这件商品后带回他的国家可以卖出的价格。小鑫只能带回m件商品，你能帮他计算一下他最多能赚多少钱么？
###输入格式:
第一行是n，m。( 0< m ≤ n ≤ 1000000 )
紧接着有n行，每一行有两个数 c ，p。第i行代表着ci，pi。( ci ≤ pi, 保证数据都在int范围内 )
###输出格式:
输出一行一个数，代表小鑫能赚多少钱。
###输入样例:
1. 4 2 2. 1 2 3. 1 3 4. 2 2 5. 3 4
输出样例:
3
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB
#include <stdio.h> struct node { int ci, pi, b; } q[1000010], t; void sort(int l, int r) { if (l >= r) return; t = q[l]; int i = l, j = r; while (i < j) { while (q[j].b <= t.b && i < j) j--; q[i] = q[j]; while (q[i].b >= t.b && i < j) i++; q[j] = q[i]; } q[i] = t; sort(l, i - 1); sort(i + 1, r); } int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) { scanf("%d %d", &q[i].ci, &q[i].pi); q[i].b = q[i].pi - q[i].ci; } sort(0, n - 1); int ans = 0; for (int i = 0; i < m; i++) { ans += q[i].b; } printf("%d\n", ans);//max return 0; }
