http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2177
題目描述
大家都知道，新生入學(xué)的前幾周要體檢，體檢的那一天 HH 早起(九點(diǎn)半)來到了校醫(yī)院，但是到了之后她發(fā)現(xiàn)排隊(duì)等候體檢的人太多了，而且人數(shù)在不斷的增加。體檢需要檢查許多個(gè)項(xiàng)目，每個(gè)項(xiàng)目都需要排隊(duì)，而且隨著時(shí)間的推移，每個(gè)隊(duì)列的人數(shù)都在慢慢增加。
已知每個(gè)體檢項(xiàng)目的隊(duì)列都有兩個(gè)屬性(ai, bi):
1、如果 HH 在 0 時(shí)刻站在了這個(gè)隊(duì)列后，那么她需要 ai 秒就可以完成這個(gè)項(xiàng)目的體檢;
2、如果 HH 沒在這個(gè)隊(duì)列中，那么 HH 完成這個(gè)項(xiàng)目的時(shí)間每秒會(huì)在 ai 的基礎(chǔ)上增加 bi 秒。
作為一個(gè)測肺活量的時(shí)候怒吹了 1000+ 的大神，她希望能盡快體檢完畢去吃飯，所以選擇正確的體檢順序是非常非常重要的。
輸入
輸入包含多組測試數(shù)據(jù)，對(duì)于每組測試數(shù)據(jù)：
輸入的第一行為一個(gè)正整數(shù) n(1 ≤ n ≤ 10
5
)，代表需要體檢的項(xiàng)目數(shù);
接下來 n 行每行為兩個(gè)正整數(shù) a，b(0 ≤ a, b < 1000), 依次代表第1-n個(gè)隊(duì)列的兩個(gè)屬性。
注意：64-bit 整型請使用 long long 來定義，并且使用 %lld 或 cin、cout 來輸入輸出，請不要使用 __int64 和 %I64d。
輸出
輸出完成體檢的最短時(shí)間，由于最后結(jié)果可能會(huì)很大，所以你只要輸出結(jié)果對(duì)365×24×60×60取余后的結(jié)果即可。
示例輸入
2
3 1
2 3
5
1 2
2 3
3 4
4 5
5 6
示例輸出
7
1419
提示
樣例解釋：
第一組樣例，最短時(shí)間：HH 先排在第二個(gè)隊(duì)伍，用時(shí) 2 秒體檢完成第二個(gè)項(xiàng)目，然后排在第一個(gè)隊(duì)伍，用時(shí) 5 秒完成第一個(gè)項(xiàng)目，總用時(shí) 7 秒。
第二組樣例，最短時(shí)間：HH 按照給定的順序， 用時(shí) 1 秒體檢完成第一個(gè)項(xiàng)目，用時(shí) 5 秒完成第二個(gè)項(xiàng)目，用時(shí) 27 秒完成第三個(gè)項(xiàng)目，用時(shí) 169 秒完成第四個(gè)項(xiàng)目，用時(shí) 1217 秒完成第五個(gè)項(xiàng)目，總用時(shí) 1+5+27+169+1217=1419 秒。
1
#include<stdio.h>
2
#include<cstring>
3
#include<algorithm>
4
#include<iostream>
5
using
namespace
std ;
6
const
int
maxn =
100010
;
7
struct
node
8
{
9
int
a,b ;
10
double
c ;
11
bool
friend
operator
<
(node x,node y)
12
{
13
return
x.c <
y.c;
14
}
15
}ss[maxn];
16
int
main()
17
{
18
int
n ;
19
while
(cin>>
n)
20
{
21
for
(
int
i =
0
; i <= n-
1
; i ++
)
22
{
23
scanf(
"
%d %d
"
,&ss[i].a,&
ss[i].b);
24
ss[i].c = ss[i].a*
1.0
/
ss[i].b;
25
}
26
sort(ss,ss+
n);
27
long
long
sum = ss[
0
].a;
28
for
(
int
i =
1
; i <= n-
1
; i ++
)
29
{
30
sum = (sum+sum*ss[i].b+ss[i].a)%(
365
*
24
*
60
*
60
);
31
}
//
取余這個(gè)地方一定不能在輸出那兒取余，因?yàn)閘onglong存不了那么大的...........
32
printf(
"
%lld\n
"
,sum);
33
}
34
return
0
;
35
}
這個(gè)題不是特別難，但是要注意，longlong是存不了太大的數(shù)據(jù)的
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
