RT,代码没发现问题。
315
280 1300
300 1200
310 1100
-1 -1
150
-32
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 100001;
bool cmp(int a, int b)
{
return a < b;
}
double calcGovAdj(int govPrice, int govQuantity, int mktPrice, int mktQuantity, int cost)
{
return (double)(mktPrice * mktQuantity - govPrice * govQuantity) / (govQuantity - mktQuantity) + cost;
}
int ceil(double a)
{
if ((int)a < a) return (int)a + 1;
return (int)a;
}
int floor(double a)
{
if ((int)a > a) return (int)a - 1;
return (int)a;
}
int main()
{
int quant[MAX], crPrice[MAX];
int count, govPrice, maxPrice, decAmt, highAdj, lowAdj, price, quantity;
double adjPrice;
cin >> govPrice;
count = 0;
while (cin >> price >> quantity && price != -1) {
crPrice[count++] = price;
quant[price] = quantity;
}
sort(crPrice, crPrice + count, cmp);
cin >> decAmt;
for (int i = 1; i < count; i++) {
int incAmt = (quant[crPrice[i]] - quant[crPrice[i-1]]) / (crPrice[i] - crPrice[i-1]);
for (int j = crPrice[i-1] + 1; j < crPrice[i]; j++) quant[j] = quant[j-1] + incAmt;
}
maxPrice = crPrice[count-1] + 1;
quant[maxPrice] = quant[maxPrice-1] - decAmt;
while (maxPrice <= govPrice) quant[maxPrice+1] = quant[maxPrice++] - decAmt;
crPrice[count++] = maxPrice;
highAdj = MAX;
lowAdj = -MAX;
for (int i = 0; crPrice[i] < govPrice; i++) {
price = floor(calcGovAdj(govPrice, quant[govPrice], crPrice[i], quant[crPrice[i]], crPrice[0]));
if (price < highAdj) highAdj = price;
}
if (crPrice[0] < govPrice) {
price = floor(calcGovAdj(govPrice, quant[govPrice], govPrice - 1, quant[govPrice-1], crPrice[0]));
if (price < highAdj) highAdj = price;
}
price = ceil(calcGovAdj(govPrice, quant[govPrice], govPrice + 1, quant[govPrice+1], crPrice[0]));
if (price > lowAdj) lowAdj = price;
for (int i = count - 1; crPrice[i] > govPrice && i >= 0; i--) {
price = ceil(calcGovAdj(govPrice, quant[govPrice], crPrice[i], quant[crPrice[i]], crPrice[0]));
if (price > lowAdj) lowAdj = price;
}
if (lowAdj > highAdj) cout << "NO SOLUTION";
else if (lowAdj <= 0) {
if (highAdj >= 0) cout << "0";
else cout << highAdj;
}
else cout << lowAdj;
return 0;
}