Description
小明是■■■星際旅游公司的員工，負(fù)責(zé)安排飛船，有N 艘飛船由他管理，每艘飛船能容納的人數(shù)都不同。今天小明被要求為一個(gè)去銻星的旅游團(tuán)安排往返的飛船，旅游團(tuán)有M人，小明希望用最少的飛船完成任務(wù)。但不是所有的飛船都能用的，地球和銻星距離K镾（此單位由銻星人發(fā)明，后在星際旅游業(yè)界廣泛使用），而每一艘飛船加滿燃料后能飛行的最長(zhǎng)路程都不一樣，除了地球上沒(méi)有別的地方能給這些飛船補(bǔ)充燃料，也不允許用一艘飛船往返多趟，也就是說(shuō)，他派出的這一批飛船必須同時(shí)帶上所有人出發(fā)，完成整個(gè)行程且能安全回來(lái)，要是選了燃料容量不夠的飛船，那些人就要在中途死光光了！敬業(yè)的小明絕對(duì)不會(huì)允許這樣的重大事故發(fā)生，當(dāng)然也不希望超載。你能幫小明算出最少需要幾艘飛船嗎？注意，當(dāng)整個(gè)行程結(jié)束后剛好耗盡燃料是允許的。

Input
第一行三個(gè)正整數(shù)N;M;K，含義見(jiàn)題面；
接下來(lái)N 行，每行兩個(gè)正整數(shù)Load_i; Fuel_i，表示這艘飛船最大載人數(shù)量和加滿燃料后的最長(zhǎng)飛行路程。
每一行的多個(gè)數(shù)用空格隔開(kāi)。

Output
一個(gè)整數(shù)，最少需要的飛船數(shù)量。無(wú)解輸出-1。

Sample Input
3 20 6
100 5
15 20
10 20

Sample Output
2
樣例說(shuō)明
第一艘飛船顯然不能用。

Data Constraint
對(duì)于20% 的數(shù)據(jù)，N ≤ 100；
對(duì)于所有數(shù)據(jù)，N ≤ 100000，題目中所有數(shù)不超過(guò)10^9。
其它重要信息見(jiàn)題面。

.
.
.
.
.
分析
水題一道
只要將飛船按照可乘坐人數(shù)從大到小排序，依次貪心地
選擇能選的飛船，統(tǒng)計(jì)答案就可以通過(guò)此題。
注意題目中劃線的重要信息寫(xiě)了地球到銻星的距離為 K，旅游團(tuán)需要往返，
所以飛船的燃料容量要大于等于 2K。

.
.
.
.
.
程序：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;long long n,m,tj=0; long long k,a[200000];inline long long read() {long long s=0,w=1;char ch=getchar();while (ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while (ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w; }int main() {n=read();m=read();k=read();k=(long long)k*2;for (int i=1;i<=n;i++){long long x,y;x=read();y=read();if (y>=k) a[++tj]=x;}if (tj==0){printf("-1");return 0;}sort(a+1,a+tj+1);int ans=0;long long rs=0;for (int i=tj;i>=1;i--){rs=(long long)rs+a[i];ans++;if (rs>=m) break;}if (rs>=m) printf("%d",ans); else printf("-1");return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/YYC-0304/p/10458934.html

總結(jié)

以上是生活随笔為你收集整理的【五校联考6day2】yi的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。