考完数电,又要开始入坑了…(●’◡’●)
链接:洛谷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;
}