JZOJ 4244. 【五校联考6day2】yi

题目

Description

小明是■■■星际旅游公司的员工，负责安排飞船，有N 艘飞船由他管理，每艘飞船能容纳的人数都不同。今天小明被要求为一个去锑星的旅游团安排往返的飞船，旅游团有M人，小明希望用最少的飞船完成任务。但不是所有的飞船都能用的，地球和锑星距离K镾（此单位由锑星人发明，后在星际旅游业界广泛使用），而每一艘飞船加满燃料后能飞行的最长路程都不一样，除了地球上没有别的地方能给这些飞船补充燃料，也不允许用一艘飞船往返多趟，也就是说，他派出的这一批飞船必须同时带上所有人出发，完成整个行程且能安全回来，要是选了燃料容量不够的飞船，那些人就要在中途死光光了！敬业的小明绝对不会允许这样的重大事故发生，当然也不希望超载。你能帮小明算出最少需要几艘飞船吗？注意，当整个行程结束后刚好耗尽燃料是允许的。

Input

第一行三个正整数N;M;K，含义见题面；
接下来N 行，每行两个正整数Load_i; Fuel_i，表示这艘飞船最大载人数量和加满燃料后的最长飞行路程。
每一行的多个数用空格隔开。

Output

一个整数，最少需要的飞船数量。无解输出-1。

Sample Input

Sample Output

2
样例说明
第一艘飞船显然不能用。

Data Constraint

对于20% 的数据，N ≤ 100；
对于所有数据，N ≤ 100000，题目中所有数不超过10^9。
其它重要信息见题面。

分析

排除不要的排序选择就好了

代码

 1 #include<iostream>
 2 #include<algorithm>
 3 #define ll long long
 4 using namespace std;
 5 ll a[1000001],w[1000001];
 6 int main ()
 7 {
 8     ios::sync_with_stdio(false);
 9     ll n,m,k;
10     cin>>n>>m>>k;
11     ll cs=0;
12     for (int i=1,x,y;i<=n;i++)
13     {
14         cin>>x>>y;
15         if (y>=2*k)
16             w[++cs]=x;
17     }
18     sort(w+1,w+1+cs);
19     ll h=0,ans=0;
20     for (int i=cs;i>=1;i--)
21     {
22         if (h<m)
23         {
24             ans++;
25             h+=w[i];
26         }
27         else
28            break;
29     }
30     if (h<m)
31         cout<<-1;
32     else
33     cout<<ans;
34 }

为何要逼自己长大，去闯不该闯的荒唐