NPSC補完計劃

登入註冊帳號.

請輸入帳號, 密碼以及預計登入時間
進階搜尋  

最新消息:

歡迎光臨NPSC補完計劃

+ NPSC補完計劃 » NPSC國中組 » NPSC2004國中組決賽
 NPSC 2004 國決 F.星光大道

作者 主題: NPSC 2004 國決 F.星光大道  (閱讀 553 次)

rscpp

  • 中級會員
  • ***
  • 文章數: 60
    • 檢視個人資料
NPSC 2004 國決 F.星光大道
« 於: 五月 15, 2015, 10:20:29 pm »

代碼: [選擇]
// npsc04-j2f (NPSC 2004 國中決 題目 F 星光大道)
// 將 ci/li 做 sort ,由最小的開始選用,至 所有 l0+l1+...lk的和 >=L 為止 , 最後一個 lk不一定用完哦
// 若用完所有的布仍不夠{即 L還有剩,則 印 Oh, NO!}
//

#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
const int maxn = 10010;
struct node
{

int e; // 布長
int c; // 價錢
double d; // 平均價
} a[maxn];
bool cmp( node x, node y)
{
return x.d < y.d;
}
int main()
{
  int i, t, L , n;
  unsigned k;
cin >> t;
while(t--)
{
cin >> L >> n;
for(i=0;i<n;++i)
{
cin >> a[i].e >> a[i].c;
a[i].d = double(a[i].c) / a[i].e;
}
sort(a, a+n , cmp);
double tot=0.0;
for(i=0; i<n; ++i)
{
if(L>=a[i].e)
{
L -= (a[i].e);
tot += (a[i].c);
} else { 
tot += (L * a[i].d);
L=0;
break; // 已舖滿 L
}
}
if(L>0) cout << "Oh, No!" << endl;
else cout << fixed << setprecision(2) << tot << endl;
}
  return 0;
}
/*
範例輸入:
3
10 2
5 2
5 3
10 2
6 2
5 3
10 2
1 1
1 1
範例輸出:
5.00
4.40
Oh, No!
*/

« 上次編輯: 五月 15, 2015, 10:23:52 pm 由 rscpp »
記錄
+ NPSC補完計劃 » NPSC國中組 » NPSC2004國中組決賽
 NPSC 2004 國決 F.星光大道