首页 > 代码库 > HDUPhysical Examination(贪心)
HDUPhysical Examination(贪心)
HDUPhysical Examination(贪心)
题目链接
题目大意:给N个队列,每个队列在0时刻体检的时候完成时间是ai,如果超过t(s),那么就是ai + t?bi.问怎样组合才能用最短的时间完成体检(每个队列都要去一趟)。结果要取模一个给定的数。
解题思路:相邻交换法,将这N个队列排下先后体检的顺序,然后在计算要花费的时间就可以了,要用long Long,ai?bi会int溢出。
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
const int MOD = 31536000;
struct Queue {
ll ai, bi;
} q[maxn];
bool cmp (const Queue A, const Queue B) {
if (A.ai * B.bi < A.bi * B.ai)
return true;
return false;
}
int main () {
int n;
while (scanf ("%d", &n) && n) {
for (int i = 0; i < n; i++)
scanf ("%I64d%I64d", &q[i].ai, &q[i].bi);
sort (q, q + n, cmp);
ll ans = q[0].ai, t = q[0].ai;
for (int i = 1; i < n; i++) {
ans = (ans + q[i].ai + (t * q[i].bi) %MOD)%MOD;
t = (t + q[i].ai + (t * q[i].bi) % MOD) % MOD;
}
printf ("%I64d\n", ans);
}
return 0;
}
HDUPhysical Examination(贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。