Lucky Draw 是如何解决的呢

描述
In the Lucky village, people are crazy on a game called Lucky Draw. In this game, N players stand in a line, and each one is assigned an integer number. Then, the village master would randomly choose K continuous players. Among these K players, the one who has the largest number will win the first prize of A dollars. Also, the one with the second smallest number will win the second prize of B dollars. Different players may have same numbers. As an agreement, only the rightmost player who has the largest number owns the first prize, and the leftmost player who has the second smallest number owns the second prize. Note that the second smallest number should be greater than the smallest number. Therefore, if all of these K players have the same number, no one will win the second prize.

A big problem in this game is about fairness. Some players may have much more chance to win prizes than others. So, the village master wants to know how fair the game is. You should tell the village master how many players have the opportunity to win the prize. In addition, you need to calculate the variance of the expected prize moneys of these potential prize winners.

输入
The first line contains four integers, N, K, A, B, as described before. (1 ≤ K ≤ N ≤ 1000000, 1 ≤ A, B ≤ 1000).

The second line contains N integers, indicate the numbers assigned to those players, listed from left to right. The numbers are guaranteed to fit in 32-bit signed integers.
输出
Output only one line containing an integer M and a real number V, separated by a single space. M is the number of players who have any chance to win the prize money. V is the variance of the expected prize money of these M players, rounded to four digits after the decimal point.
样例输入
6 3 1 2
1 2 1 3 3 3
样例输出
4 0.1719

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问