C++(g++ 7.5.0)(g++7.5.0) 解法, 执行用时: 4ms, 内存消耗: 524K, 提交时间: 2022-09-12 14:13:14

#include <iostream>
#include <cmath>
using namespace std;
int a[100010][3];//用于存放价格和销量的数组
int main()
{
	int i = 1, j = 1, k, expect, down, max, temp, cha, xl, num, s, price, p;
	cin >> expect;//读入预期价
	while (cin >> a[i][1] >> a[i][2] && a[i][1] != -1 && a[i][2] != -1)//如果输入的两个数不是-1，-1
	{
		i++;//循环变量i++
		if (i > 2 && a[i - 1][1] - a[i - 2][1] > 1)//如果两个价格之间差大于一
		{
			i--;//回到上一个读入的销量
			cha = (a[i - 1][2] - a[i][2]) / (a[i][1] - a[i - 1][1]);//求出每次销量减少多少：销量差/价格差
			temp = a[i][1];//记录下价格
			for (j = a[i - 1][1] + 1; j <= temp; j++)//按价格递增顺序依次写入
			{
				a[i][1] = j;//写入价格
				a[i][2] = a[i - 1][2] - cha;//按销量差写入销量
				i++;
			}
		}
	}
	cin >> down;//输入超过最大价格之后每次销量降低多少
	i--;//因为上面的while循环最后有i++所以用i--抵消……
	xl = a[i][2];//记录目前的销量
	while (xl > 0)
	{
		if (xl - down < 0)break;//如销量小于零则退出
		else//否则
		{
			xl -= down;
			i++;
			a[i][1] = a[i - 1][1] + 1;
			a[i][2] = xl;
		}
	}
	for (j = 1; j <= 10000; j++)
	{
		max = -99999;
		for (k = 1; k <= i; k++)
		{
			num = (a[k][1] - a[1][1] + j) * a[k][2];
			if (num >= max)
			{
				max = num;
				price = a[k][1];
				p = 1;
			}
		}
		if (price == expect) { cout << j * p; return 0; }
			max = -99999;
		for (k = 1; k <= i; k++)
		{
			num = (a[k][1] - a[1][1] - j) * a[k][2];
			if (num >= max)
			{
				max = num;
				price = a[k][1];
				p = -1;
			}
		}
		if (price == expect) { cout << j * p; return 0; }
	}
}

C++14(g++5.4) 解法, 执行用时: 12ms, 内存消耗: 604K, 提交时间: 2019-09-09 14:01:44

#include <bits/stdc++.h>
using namespace std;

const int maxn = 100000;
int sale[maxn];
int earn[maxn];
int main() {
	int expect; cin >> expect;
    int t1, t2; cin >> t1 >> t2;
    sale[t1] = t2;
    int cost = t1;
    int last_t1 = t1;
    while (cin >> t1 >> t2 && t1 != -1) {
        sale[t1] = t2;
        int k = last_t1 + 1;
        while (k != t1) {
            sale[k] = sale[last_t1] + (sale[t1] - sale[last_t1] ) * (k - last_t1) / (t1 - last_t1);
            k++;
        }
        last_t1 = t1;
    }
    int dec; cin >> dec;
    while (sale[last_t1] > 0) {
        last_t1++;
        sale[last_t1] = sale[last_t1 - 1] - dec;
    }

    int k = 0;
    while (true) {
        for (int i = 0; i < last_t1; i++) {
            earn[i] = (i + k - cost) * sale[i];
            if (earn[i] <= 0) continue;
        }
        if (*max_element(earn, earn + maxn) == earn[expect] ){//                && count(earn, earn + maxn, earn[expect]) == 1) {
            cout << k << endl;
            return 0;
        }
        for (int i = 0; i < last_t1; i++) {    //
            earn[i] = (i - k - cost) * sale[i];
        }
         if (*max_element(earn, earn + maxn) == earn[expect] ){//} && count(earn, earn + maxn, earn[expect]) == 1) {
            cout << -k << endl;
            return 0;
        }
        k++;
    }
}

C++ 解法, 执行用时: 4ms, 内存消耗: 400K, 提交时间: 2021-06-18 17:59:46

#include <bits/stdc++.h>
int expect, cost[100000], sale[100000], len, c, s, d, maxpos, maxneg;
int main() {
  scanf("%d%d%d", &expect, cost, sale);
  while (~scanf("%d%d", &c, &s)&&~c&&~s) {
    d=(s-sale[len])/(c-cost[len]);
    for (int i=cost[len]+1; i<=c; i++, len++) {
      cost[len+1]=i;
      sale[len+1]=sale[len]+d;
    }
  }
  scanf("%d", &d); d=-d;
  for (int i=cost[len]+1; sale[len]+d>0; i++, len++) {
    cost[len+1]=i;
    sale[len+1]=sale[len]+d;
  }
  for (int i=1; ; i++) {
    maxpos=maxneg=0;
    for (int j=1; j<=len; j++) {
      if (sale[j]*(cost[j]-cost[0]+i)>=sale[maxpos]*(cost[maxpos]-cost[0]+i))
        maxpos=j;
      if (sale[j]*(cost[j]-cost[0]-i)>=sale[maxneg]*(cost[maxneg]-cost[0]-i))
        maxneg=j;
    }
    if (cost[maxpos]==expect) {
      printf("%d", i); break;
    } else if (cost[maxneg]==expect) {
      printf("%d", -i); break;
    }
  }
  return 0;
}