首页 > ACM题库 > HDU-杭电 > HDU 3273-Lottery-分治-[解题报告]HOJ
2014
03-13

HDU 3273-Lottery-分治-[解题报告]HOJ

Lottery

问题描述 :

Your living city is holding a big lottery game now! There are M people in this city who want to play this lottery. Everyone of them must pay C dollars to get a lottery ticket. Taking this ticket, he can get a chance to win a prize by randomly selecting one from N indistinguishable boxes and getting the prize if there is a ball in the selected box. The ball in the selected box is also taken by this winner, so if a box with a ball happens to be selected by a player, it will never contain balls from then on, but it will be closed and can be selected by the future players. Every box contains exactly one ball at the beginning, and two or more players cannot select the boxes and the same time.

Of course, the latter you join this game, the less the chance you win a prize will be. So the lottery holder make such a rule: If you are the n-th player who wins a prize, you will get A*(n-1)+B dollars. That is to say, the first winner will get B dollars, the second winner will get A+B dollars, the income of the third winner is 2*A+B, and so on.

Being curious about the expected profit, the lottery holder is too lazy to calculate it himself. So he finds you and give you a lot of money to do this work. If you can solve it quickly, you will be a millionaire!

输入:

The first line of input is a integer T, the number of test cases. Each case contains exactly 5 integers M, N, C, A, B in this order, where 1 <= M, N <= 10^6 and 0 <= C, A, B <= 100.

输出:

The first line of input is a integer T, the number of test cases. Each case contains exactly 5 integers M, N, C, A, B in this order, where 1 <= M, N <= 10^6 and 0 <= C, A, B <= 100.

样例输入:

3
1 2 10 5 7
2 2 10 5 7
7 5 0 0 1

样例输出:

3
7
-3.95142

不一样的二分;

思路:

    *二分的上限下限是:MAX(最大的数字),SUM (总和);

    *其中一定有一个数字满足,将N分成M份;

    *求最小的;只要当它达到M份时,依然减小上届值;


算法不难,思路想到了就 水到渠成了;

/*  
 *problem ID: POJ 3273
 * Author ID: fuqiang  
 *      TIME: 2013-07-17  
 * Algorithm: 二分 
 *    Status: (Accept)  
*/  
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <iomanip>
#define maxn 100010
int a[maxn],N,M;
using namespace std;
inline bool check(int mid)
{
	int num = 1, sum = 0;
	for(int i = 0; i <= N; i++)
	{
		if(sum + a[i] <= mid)
			sum += a[i];
		else
		{
			sum = a[i];
			num++;
		}
	}
	return num>M;
}
int main(int argc, char *argv[])
{
	while(scanf("%d%d",&N,&M)!=EOF)
	{
		int MAX = 0, sum = 0;
		for(int i = 1; i <= N; i++)
		{
			scanf("%d",&a[i]);
			sum += a[i];
			MAX = max(MAX,a[i]);
		}
		int left = MAX, right = sum, mid;
		while(left < right)
		{
			mid = (left + right) / 2;
			if(check(mid))
				left = mid + 1;
			else
				right = mid - 1;
		}
		printf("%d\n",left); 
	}
	return 0;
}

参考:http://blog.csdn.net/i_fuqiang/article/details/9357105