2014
02-21

# The skatepark’s new ramps

The local skating park has been given a nancial incentive by the city to make the park interesting for skaters of all levels. The park wants to use the incentive to build a series of ramps, somewhat resembling a mountain range. When talking to some of the volunteers in the committee responsible for the project, you find out they’re having diffculties deciding about the best con guration of the ramps. They know the number of ramps to be built, and for each ramp they agree on the range of the height for that ramp. They are still discussing exactly how high each ramp should be, since they can’t a ord to have them all at their highest, but they do want to spend all of the budget. This is the most important issue in the debate: they can’t agree whether they want the di erences between the ramps to be small, to give the full ride a more consistent feeling, or as big as possible, to create a more diverse set of challenges.

You also notice they don’t really have a good idea what the possibilities are, leaving them stranded in ‘what-if’ discussions. You decide to help them out by showing them the options they have, both the ones where the di erence between the highest and lowest ramp is kept as small as possible, as well as the one where that di erence is as much as possible. Since the committee is mainly bickering over the allowable di erences, you decide to start out by just presenting them the minimum and maximum di erence-between the highest and lowest ramp. Luckily, the park has a lot of space, so you won’t need to take the placement of the ramps into account. All ramps
have the same inclination, which is such that a ramp of height h will have a length 4h (measured at, not over the ramp).

The rst line of input consists of the integer number n, the number of test cases;
Then, for each test case:
A line with the integer number r (2 <=r<=10000), the number of ramps the park will place;
A line with the integer number m (0 <= m <=200000000 = 2*10^8), the number of cubic meters of concrete the park has money for;
r lines with two numbers, l and t (0.00 <=l <=t <= 100.00), separated by one space, the minimum and maximum height in meters of the r-th ramp.

You may assume all ramps are made entirely of concrete, and shaped as 1 meter wide prisms, with a triangle with two equal sides as base. A series of ramps within the given constraints and using all concrete is guaranteed to exist.

The rst line of input consists of the integer number n, the number of test cases;
Then, for each test case:
A line with the integer number r (2 <=r<=10000), the number of ramps the park will place;
A line with the integer number m (0 <= m <=200000000 = 2*10^8), the number of cubic meters of concrete the park has money for;
r lines with two numbers, l and t (0.00 <=l <=t <= 100.00), separated by one space, the minimum and maximum height in meters of the r-th ramp.

You may assume all ramps are made entirely of concrete, and shaped as 1 meter wide prisms, with a triangle with two equal sides as base. A series of ramps within the given constraints and using all concrete is guaranteed to exist.

1
3
36
1.00 4.00
1.00 4.00
1.00 4.00

0.00 3.00

Hint

Figure 1: The example ramps with maximum difference.


1. if(j){
int ans=a ;
for(int x=j-1;x>=0;x–){
if(!a ) break;
ans=min(ans,a );
sum+=ans;
}
}
求解释，，dp的思路是什么呢？

2. 第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。第2题，TCP不支持多播，多播和广播仅应用于UDP。所以B选项是不对的。

3. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。