贪心算法（又称贪婪算法)是指，在对问题求解时，总是做出在当前看来是更好的选择。也就是说，不从整体更优上加以考虑，他所做出的是在某种意义上的局部更优解。

贪心算法不是对所有问题都能得到整体更优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

肥鼠贸易

肥鼠贸易

时间限制： 2000/1000毫秒(Java/其他)内存限制： 65536/32768K(Java/其他)

提交总数： 33703已接受的提交： 10981

问题描述

FatMouse准备了M磅的猫粮，准备和看守仓库的猫交易，仓库里有他最喜欢的食物JavaBean .

仓库有普通个房间。个房间有J磅的JavaBeans，需要F磅的猫粮FatMouse .不必用房间里的所有爪哇咖啡豆进行交易，相反，如果他支付F[i]* a%磅的猫粮，他可能会得到J[i]* a%磅的JavaBeans .这里a是实数。现在他给你布置了这个作业，告诉他他能获得的更大爪哇咖啡豆数量。

投入

输入由多个测试用例组成。每个测试用例以一行包含两个非负整数M和普通开始，然后是普通行，每一行分别包含两个非负整数J[i]和F[i].最后一个测试用例后面是两个1。所有整数都不大于1000。

输出

对于每个测试用例，在一行中打印一个到小数点后3位的实数，这是FatMouse可以获得的爪哇咖啡豆的更大数量。

样本值输入

5 3

7 2

4 3

5 2

20 3

25 18

24 15

15 10

-1 -1

抽样输出

13.333

31.500

贪心思想

从每傍食物更便宜的开始

C代码

C

# includeiostream

#includealgorithm

使用命名空间标准；

struct bean{

双倍英镑；

双重价值；

双重扩散；

布尔运算符（常量豆A)常量{

返回变态

}

} buff[100]；

int main(){

int n；

双m；

while(cinmn){

if(m==-1n==-1)break；

for(int I=0；I n；i ){

scanf('%lf%lf '，buff[i].磅，buff[i].值);

buff[i].perv=buff[i].英镑/英镑。价值；

}

sort(buff，buff n)；

int id=0；

double ans=0；

while(m 0 id n){

if(m buff[id]).值){

m -=buff[id].价值；

ans=buff[id].英镑；

}else{

ans=m*buff[id].性欲倒错者

m=0；

}

id；

}

coutansendl

}

返回0;

}

/*

5 3

7 2

4 3

5 2

20 3

25 18

24 15

15 10

-1 -1

*/

一

2

3

四

5

6

七

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

# includeiostream

#includealgorithm

使用命名空间标准；

struct bean{

双倍英镑；

双重价值；

双重扩散；

布尔运算符（常量豆A)常量{

返回变态

}

} buff[100]；

int main(){

int n；

双m；

while(cinmn){

if(m==-1n==-1)break；

for(int I=0；I n；i ){

scanf('%lf%lf '，buff[i].磅，buff[i].值);

buff[i].perv=buff[i].英镑/英镑。价值；

}

sort(buff，buff n)；

int id=0；

double ans=0；

while(m 0 id n){

if(m buff[id]).值){

m -=buff[id].价值；

ans=buff[id].英镑；

}else{

ans=m*buff[id].性欲倒错者

m=0；

}

id；

}

coutansendl

}

返回0;

}

/*

5 3

7 2

4 3

5 2

20 3

25 18

24 15

15 10

-1 -1

*/

今年暑假不英亩

"今年暑假不AC？”

"是的。"

"那你干什么呢？"

"看世界杯呀，笨蛋!"

"@#$%^*%…"

确实如此，世界杯来了，球迷的节日也来了，估计很多埃克米尔也会抛开电脑，奔向电视了。

作为一个球迷，你一定想看尽可能多的完整比赛。当然，作为一个新时代的好青年，一定要看一些其他的节目，比如新闻联播(念念不忘大事)、超女、王的《开心辞典》等。如果你已经知道你喜欢看的所有电视节目的播出时间表，你会合理安排吗？目标是看尽可能多的完整节目

投入

输入数据包含多个测试用例。每个测试用例的行只有一个整数n(n=100)，表示你喜欢看的节目总数，然后有n行数据，每行包括两个数据ti _ s和ti _ e (1=i=n)，分别表示第I个节目的开始和结束时间。为了简化问题，每个时间用正整数表示。N=0表示输入结束，不做任何处理。

输出

对于每个测试用例，输出能完整看到的电视节目数，每个测试用例的输出占用一行。样本值输入

12

1 3

3 4

0 7

3 8

15 19

15 20

10 15

8 18

6 12

5 10

4 14

2 9

0

贪婪的想法

根据结束时间，先看早结束时间

c代码

C

# includeiostream

#includealgorithm

使用命名空间标准；

结构程序{

int start

int endx

布尔运算符(常量程序A)常量{

返回endx A.endx

}

} buff[10000]；

int main(){

int n；

while(cinn){

if(n==0)break；

int ans=1，time=0；

for(int I=0；I n；i ){

cinbuff[i]。startbuff[i]。endx

}

sort(buff，buff n)；

time=buff[0]。endx

for(int I=1；I n；i ){

if(buff[i]。start=time){

ans

时间=buff[i]。endx

}

}

coutansendl

}

返回0；

}

一个

2

三

四

五

六

七

八

九

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

# includeiostream

#includealgorithm

使用命名空间标准；

结构程序{

int start

int endx

布尔运算符(常量程序A)常量{

返回endx A.endx

}

} buff[10000]；

int main(){

int n；

while(cinn){

if(n==0)break；

int ans=1，time=0；

for(int I=0；I n；i ){

cinbuff[i]。startbuff[i]。endx

}

sort(buff，buff n)；

time=buff[0]。endx

for(int I=1；I n；i ){

if(buff[i]。start=time){

ans

时间=buff[i]。endx

}

}

coutansendl

}

返回0；

}