P1023 (tax and subsidy issues)

Topic background

The lower the price of each commodity, the higher the sales volume. Now we know the cost of a commodity and its sales volume at several prices (the product will not be lower than the sales cost), and assume that the change of sales volume between adjacent prices is linear, and after the price is higher than the given maximum price, the sales volume decreases by a fixed value. (we assume that both price and sales volume are integers)
For some special commodities, it is impossible for the market to adjust their prices completely. At this time, the government needs to control it in the form of taxes or subsidies. (the so-called tax or subsidy is the currency in which a fixed amount is charged or given to the manufacturer for each product)

Title Description

You are the project manager of a consulting company. Now you know the expected price of a certain commodity by the government and the sales situation at various prices. You are required to determine whether the government should pay tax or the minimum amount of subsidy (also an integer) for this commodity, so as to enable businesses to obtain the maximum total profit compared with other prices at such a price expected by the government.
Total profit = profit per unit commodity × sales volume
Unit commodity profit = unit commodity price - unit commodity cost (- tax or + subsidy)

Input format

The first line of input is the expected price of a certain commodity by the government. The second line has two integers. The first integer is the cost of the commodity, and the second integer is the sales volume at the cost price. Each line of the following lines has two integers, the first is the unit price at a certain price, and the second is the sales volume at this time. A line of - 1 − 1, - 1 − 1 indicates that all known prices and corresponding sales volume have been entered, The behavior of increasing the highest unit price of each known dollar indicates that the last dollar will decrease the highest unit price of each known dollar.

Input format

There are two cases of output: if the maximum total profit can be obtained from the expected price of the government, a separate integer will be output. The positive and negative of the number indicates whether it is subsidy or tax collection, and the size of the number indicates the minimum amount of subsidy or tax collection. If there are multiple solutions, take the output with the smallest absolute value.
If the maximum total profit cannot be obtained at the expected price of the government, "NO SOLUTION" will be output.

Problem solving ideas

How troublesome! There may be several numbers between the two connected numbers, which need to be supplemented manually. I saw some big men solving inequality equations. However, I have a good head of weak chicken, so I chose the method of violent search, but in fact, there is a pit in violent search, that is, we can't judge whether there is a solution. Then we just start from reality and think that the value of government subsidies or taxes will not be greater than the value of goods, In this way, violent search has a boundary. There is also the last test point. I always make mistakes when I use float. I use matlab to check the calculation (Matlab is really fragrant). I use double to quickly ac.

code

#include<iostream>
using namespace std;
double yuce;
double dt[100010][2];
double down;
int main() {
	cin >> yuce;
	int i = 1;
	while ((dt[i-1][0]!=-1)||(dt[i-1][1]!=-1)) {
		cin >> dt[i][0] >> dt[i][1];
		i++;
	}
	i -= 2;
	cin >> down;
	double k = 0;
	while (k<=100000) {
		double max = 0;
		double temp = 0;
		for (int j = 1;j < i;j++) {
			double m = dt[j][0];
			double s = dt[j][1];
			double xh = (dt[j + 1][1] - dt[j][1]) / (dt[j + 1][0] - dt[j][0]);
			while (m < dt[j + 1][0]) {
				double zlr = (m - dt[1][0] + k)*s;
				if (zlr >= max) {
					max = zlr;
					temp = m;
				}
				m++;
				s += xh;
			}
		}
		double m = dt[i][0];
		double s = dt[i][1];
		while (s>0) {
			double zlr = (m - dt[1][0] + k)*s;
			if (zlr >= max) {
				max = zlr;
				temp = m;
			}
			m++;
			s -= down;
		}
		if (temp == yuce) {
			cout << k << endl;
			return 0;
		}
		max = 0;
		temp = 0;
		for (int j = 1;j < i;j++) {
			double m = dt[j][0];
			double s = dt[j][1];
			double xh = (dt[j + 1][1] - dt[j][1]) / (dt[j + 1][0] - dt[j][0]);
			while (m < dt[j + 1][0]) {
				double zlr = (m - dt[1][0] - k)*s;
				if (zlr >= max) {
					max = zlr;
					temp = m;
				}
				m++;
				s += xh;
			}
		}
		m = dt[i][0];
		s = dt[i][1];
		while (s > 0) {
			double zlr = (m - dt[1][0] - k)*s;
			if (zlr >= max) {
				max = zlr;
				temp = m;
			}
			m++;
			s -= down;
		}
		if (temp == yuce) {
			cout << (-1)*k << endl;
			return 0;
		}
		k++;
	}
	cout << "NO SOLUTION" << endl;
	return 0;
}

Tags: C++

Posted by modcar on Tue, 24 May 2022 15:53:06 +0300