Determine the Price（ZJU 2002）

Determine the Price

时间限制: 1 Sec 内存限制: 128 MB

题目描述

For the manager of a theatre, setting the price of a ticket is a rather delicate matter. Suppose that a theatre has n (<= 1000000) seats, and that if you give away the tickets for free, all the seats will be taken. After some sort of investigation, it is estimated that for every p yuans of increase of the ticket price, the theatre will lose m audiences. But the audiences will not leave until the ticket price jumps up a complete step of p yuans. For example, if given p=1.00 and m=10, no audience will be lost if the price is set to be 0.99 yuans, and 10 will be lost if the price is 1.99 yuans. It costs R yuans for the theatre to run each show, and S yuans to serve each of the audiences during each show. Now your job is to write a program to maximize the total revenue of each show for the theatre.

输入

The first line of input contains a positive integer N (< 10000), then followed by N test cases.

Each test case consists of 5 positive numbers in a line, n, p, m, R, S which are all defined in the problem.

输出

For each test case, print the optimal price of a ticket, the total number of audiences to sit in the theatre with that price set, and the maximum revenue, in the format illustrated by the sample output.

Note: the unit of price is RMB yuan, and a price must be rounded off to 2 decimal places. There must be one blank line between two test cases, but no extra line at the end of output.

样例输入

复制样例数据

2
1000 0.10 10 1000 2.00
100 0.50 2 500 2.0

样例输出

price = 6.09
audiences = 400
revenue = 636.00

price = 13.99
audiences = 46
revenue = 51.54

数学解法：我们可以很轻易的得到这样一个二次函数。

Y = PK*（N – MK）- R -（N- MK）S
Y表示收益， K表示票价上升的倍数。则整理得：

Y= -PMK^2 + (PN + MS)S – NS – R

二次函数的顶点坐标为 ( - b / 2a , (4ac-b^2)/4a ) ,

此函数的顶点X坐标为 – b / 2a = - (PN + MS) / 2*(-PM) = (PN + MS) / 2PM

得到这个值，则为最优值，但不能保证精确（因为毕竟答案只取2位小数），所以我们加以部分枚举，枚举 X – 10 ~ X + 10，这样就可以保证答案的正确性了。

得到了X，可以计算各个值了：

Price = P * X – 0.01
Audiences = N - M * ( X - 1 )
Revenue = Price * Audiences - R - S * Audiences

/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

typedef long long LL;
using namespace std;

int t;
double p, s, m, r, n;

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	scanf("%d", &t);
	for (int cas = 1; cas <= t; cas++){
		//if(cas != 1) printf("\n");
		scanf("%lf %lf %lf %lf %lf", &n, &p, &m, &r, &s);
		int t = (p * n + m * s) / (2 * p * m);
		double revenue = 0, pri;
		int au;
		for (int i = t - 10; i <= t + 10; i++){
			double sum = (p * i - 0.01 - s) * (n - m * (i - 1)) - r;
			if(sum > revenue) revenue = sum, pri = p * i - 0.01, au = n - m * (i - 1);
		}
		printf("price = %.2lf\n", pri);
		printf("audiences = %d\n", au);
		printf("revenue = %.2lf", revenue);
		if(cas != t) printf("\n\n");
	}

	return 0;
}
/**/

/*100 0.50 100 500 2.0*/

好久没写博客了，有很多数论的题目没总结呢，与其说是没时间，还不如说是懒得写，哎。。