洛谷P1023 税收与补贴问题

考完数电,又要开始入坑了…(●’◡’●)

链接:洛谷P1023

这题理解题意很重要啊,我看了半天它的样例,感叹这样例都不是线性的啊,后来发现是我理解题意错了,相邻价位的销量变化是线性的,这里指的是给出的相邻价位之间的销量变化是线性的,然后中间空缺的价位销量就要依靠此求出.

要求绝对值最小,一开始我直接min(fabs(resMin),fabs(resMax)),这是不对的,在可行解区间左右端点一正一负的情况下,显然绝对值最小的点是0啊. 说明可行解区间的概念在写的时候还没想清楚.还是不够熟练.

code:

#include <time.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

#define maxn 200005
#define lowbit(x) (x & -x)
typedef long long ll;
typedef unsigned long long ull;

int price[100005];
int num[100005];

int main() {
  // clock_t start,end;
  // start=clock();
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int a,n;
  cin>>a;
  int x,y;
  int m=1;
  int maxprice=0;
  cin>>price[1]>>num[1];
  while(cin>>x>>y&&x!=-1&&y!=-1){
    while(x>price[m]+1){
        ++m;
        price[m]=price[m-1]+1;
        num[m]=num[m-1]+(y-num[m-1])/(x-price[m-1]);
        if(price[m]==a) n=num[m];
       // cout<<"*"<<price[m]<<" "<<num[m]<<endl;
    }
    price[++m]=x;
    num[m]=y;
    if(price[m]==a) n=num[m];
    maxprice=max(x,maxprice);
   // cout<<"*"<<price[m]<<" "<<num[m]<<endl;
  }
  int less;
  cin>>less;

  int j=maxprice+1;
  for(;;j++){
    if(num[m]-less<=0) break;
    price[++m]=j;
    num[m]=num[m-1]-less;
    if(price[m]==a) n=num[m];
   // cout<<"*"<<j<<" "<<num[m]<<endl;
  }
  int resMax=100000;
  int resMin=-100000;
  for(int i=1;i<=m;i++){
    if(price[i]==a) continue;
    double temp=1.0*((ll)price[i]*num[i]-a*n)/(n-num[i])+price[1];
      if(n>num[i]){
        resMin=max(resMin*1.0,ceil(temp));
      } 
      if(n<num[i]){
        resMax=min(resMax*1.0,floor(temp));
      }
  }
 // cout<<resMin<<"$ "<<resMax<<endl;
  if(resMin>resMax) cout<<"NO SOLUTION"<<endl;
  else if(resMin>0) cout<<ceil(resMin)<<endl;
  else if(resMax<0) cout<<floor(resMax)<<endl;
  else cout<<0<<endl;
  // end=clock();
  // cout<<"TIME PASSED:"<<end-start<<endl;
  return 0;
}