洛谷P1478 陶陶摘苹果(升级版)
题目
输入格式
输出格式
只有一个整数,表示陶陶最多能摘到的苹果数。
输入输出样例
输入
8 15
20 130
120 3
150 2
110 7
180 1
50 8
200 0
140 3
120 2
输出
4
说明/提示
原题地址->link
分析
关于这道题,我首先想说的是,题目暗含了一个条件,就是,陶陶摘苹果是挑着摘的,而且,挑的原则是哪个摘起来省力,就摘那个。这好像就是一个潜规则一样。而且这个隐含条件不好想。我开始的时候,是觉得那个高度低我就摘哪个,发现,怎么着都不对。后来,我是这样想的,陶陶在摘之前,需要搬凳子,哪个搬起来省劲,就这样整。不知道,这样想对不对。如果,哪位大佬知道为什么按照力气挑苹果,请在下方留言,大家一起讨论下。
此外,还有一个点需要注意,就是,陶陶自己知道搬不动,就不会去搬,然后找下一个苹果。
Code
#include <iostream>
#include <algorithm>
using namespace std;
typedef struct {
int high,need_power;
}Apple;
bool compare(Apple a,Apple b)
{
return a.need_power<b.need_power;
}
int main()
{
int n,power,count=0;//count->可以摘到的苹果
cin >> n >> power;
int chair_high=0,hand_high=0;//凳子的高度,手可以达到的高度
cin >> chair_high >> hand_high;
Apple apple[n];
for (int i = 0; i < n; ++i) {
cin >> apple[i].high >> apple[i].need_power;
}
sort(apple,apple+n,compare);
for (int i = 0; i < n; ++i) {
power-=apple[i].need_power;
if(power>=0&&(chair_high+hand_high-apple[i].high)>=0)
count++;
else power+=apple[i].need_power;
}
cout << count;
return 0;
}