首页 > 代码库 > BNUOJ 44662 水题 (贪心+优先级队列)
BNUOJ 44662 水题 (贪心+优先级队列)
水题
Time Limit: 500ms
Memory Limit: 32768KB
This problem will be judged on HRBUST. Original ID: 222364-bit integer IO format: %lld Java class name: Main
Prev
Submit Status Statistics Discuss
Next因为是有关于接水的问题,便简称为水题了(。
N个人排队在M个出水口前接水,第i个人接水需时为t[i],
请问接水的最短用时是多少?
Input
第一行一个整数 T ,代表有 T 组数据。
每组数据
第一行两个整数 N(<=100000) , M(<=10000) 代表有 N 个人 M 个出水口。
第二行N个整数,第i个数字t[i](<=10000)代表第i个人接水用时t[i]。
Output
对于每组数据输出一个整数,代表所需的最少接水时间。
Sample Input
2
5 3
1 2 3 4 5
6 3
1 2 3 3 4 5
Sample Output
5
6
Hint
小桥流水哗啦啦,我和小岛去偷瓜~。
Source
"诚德软件杯"哈尔滨理工大学第四届ACM程序设计团队赛
解析:就是一个贪心思想,就像往一个瓶子里装核桃和沙子一样,怎么样才能在有限的空间里容纳更多重量,那就是先尽可能装最多大的,让后再处理小的,同样我们这题的思想也是,尽可能的先把最大的处理了,直到处理完为止。按从大到小的顺序处理,先加入m个最大的元素进入队首为最小元素的优先级队列,然后再不断从队首取出元素(队首为队列中的最小值),让它加上当前未加入的最大元素,再放入队列中,重复上述操作,直到把所有的n-m个全部加进去即可,此时队列中的最大值(也就是队尾元素),就是答案。
AC代码:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <cstdlib> #include <ctime> using namespace std; #define INF 0x7fffffff #define LL long long #define MID(a, b) a+(b-a)/2 const int maxn = 1000 + 10; #pragma comment(linker, "/STACK:1024000000,1024000000") template <class T> inline bool scan_d(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; //EOF while(c!=' -' &&(c<'0' ||c>'9' )) c=getchar(); sgn=(c==' -' )?-1:1; ret=(c==' -' )?0:(c-'0' ); while(c=getchar(),c>='0' &&c<='9' ) ret=ret*10+(c-'0' ); ret*=sgn; return 1; } inline void out(int x) { if(x>9) out(x/10); putchar(x%10+'0' ); } int a[100005]; int main(){ #ifdef sxk freopen("in.txt", "r", stdin); #endif // sxk std::ios::sync_with_stdio(false); std::cin.tie(0); int t, n, m; scanf("%d", &t); while(t--){ priority_queue<int, vector<int>, greater<int> > p; //最小值优先的优先级队列 scanf("%d%d", &n, &m); for(int i=0; i<n; i++) scanf("%d", &a[i]); sort(a, a+n); for(int i=n-1; i>=0; i--){ if(i >= n-m) p.push(a[i]); //先入队m个 else{ int x = p.top(); p.pop(); p.push(x + a[i]); } } int ans; while(p.size()){ ans = p.top(); p.pop(); } printf("%d\n", ans) ; } return 0; }
BNUOJ 44662 水题 (贪心+优先级队列)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。