7-7 sdut-C语言实验-懒虫小鑫
分数 20
全屏浏览
切换布局
作者 马新娟
单位 山东理工大学
小鑫是个大懒虫，但是这一天妈妈要小鑫去山上搬些矿石去城里卖以补贴家用。小鑫十分的不开心。不开心归不开心，小鑫还是要做这件事情的。
我们把这个事情简化一下。有n块矿石，设第i块矿石由两个数字wi和pi表示。分别表示这块石头的重量和可以卖的价钱。小鑫每次只能搬一块矿石去城里卖，所以他决定每次都会搬重量最小的那块。如果恰好有几块重量相等，那就在这几块中挑选价值最高的带走。
由于路程原因。小鑫每天只能打m个来回，也就意味着他只能卖掉m块矿石。你能计算出他能得到多少钱么？
###输入格式:
第一行为n，m。m≤n≤10000。
接下来有n行，每行两个数代表石头的w与p。
###输出格式:
对于每组数据，输出有一行为一个数，为答案。
###输入样例:
1. 4 2 2. 1 2 3. 1 3 4. 2 2 5. 3 4
###输出样例:
5
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
栈限制
8192 KB
#include <stdio.h> #include <stdlib.h> #include <string.h> struct node { int p, h; } a[10001], t; void sort(int l, int r) //快排 { t = a[l]; int i = l, j = r; if (l >= r) return; while (i < j) { while ((a[j].h > t.h || (a[j].h == t.h && a[j].p <= t.p)) && i < j) j--; a[i] = a[j]; while ((a[i].h < t.h || (a[i].h == t.h && a[i].p >= t.p)) && i < j) i++; a[j] = a[i]; } a[i] = t; sort(l, i - 1); sort(i + 1, r); } int main() { int n, m; while (~scanf("%d %d", &n, &m)) { for (int i = 0; i < n; i++) { scanf("%d %d", &a[i].h, &a[i].p); } sort(0, n - 1); int ans = 0; for (int i = 0; i < m; i++) ans += a[i].p; printf("%d\n", ans); }//max return 0; }
