- #include<stdio.h>
- typedef struct product{
- int price;
- int sale;
- }Product;
- int main(void){
- int expect;
- int price, sale;
- int ogPrice, ogSale, maxPrice=0;
- Product p[10050];
- for(int i=0; i<10050; i++){
- p[i].sale = 0;
- p[i].price = 0;
- }
- scanf("%d", &expect);
- scanf("%d%d", &price, &sale);
- maxPrice = ogPrice = price;
- ogSale = sale;
- p[ogPrice].price = price;
- p[ogPrice].sale = sale;
- while(1){
- scanf("%d%d", &price, &sale);
- if(price==-1 && sale==-1)
- break;
- p[price].price = price;
- p[price].sale = sale;
- if(price> maxPrice)
- maxPrice = price;
- }
- int dec;
- Product be, af;// 前驱后继
- scanf("%d", &dec);
- for(int i=ogPrice; i<10050; i++){
- if(p[i].price == 0){
- p[i].price = i;
- if(p[i].price> maxPrice)
- p[i].sale = p[i-1].sale - dec;
- else{
- for(int j=i-1; j>=ogPrice; j--){
- if(p[j].price != 0)// 说明被赋过值
- be = p[j];
- break;
- }
- for(int j=i+1; j<10050; j++){
- if(p[j].price != 0){
- af = p[j];
- break;
- }
- }
- p[i].sale = be.sale+((af.sale - be.sale)/(af.price - be.price));
- }
- }
- if(p[i].sale <= 0)
- break;
- }
- int maxId = -1;
- int maxProfit = -1;
- int profit;
- int add = 0, minus = 0;
- while(maxId != expect && add <10000){
- maxId = -1;
- maxProfit = -1;
- for(int i=ogPrice; i<10050; i++){
- if(p[i].sale <= 0)
- break;
- profit = (p[i].price-p[ogPrice].price+add)*p[i].sale;
- if(profit>= maxProfit){
- maxId = i;
- maxProfit = profit;
- }
- }
- add++;
- }
- if(maxId == expect)
- add--;
- else
- add = 100000;
- maxId = -1;
- maxProfit = -1;
- while(maxId != expect && minus*(-1) <10000){
- maxId = -1;
- maxProfit = -1;
- for(int i=ogPrice; i<10050; i++){
- if(p[i].sale <= 0)
- break;
- profit = (p[i].price-p[ogPrice].price+minus)*p[i].sale;
- if(profit>= maxProfit){
- maxId = i;
- maxProfit = profit;
- }
- }
- minus--;
- }
- if(maxId == expect){
- ++minus;
- }
- else
- minus = -100000;
- if(add == 100000 && minus == -100000)
- printf("NO SOLUTION");
- else if(add < minus*(-1))
- printf("%d", add);
- else
- printf("%d", minus);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3115817.html