P 1023税収と補助金問題(洛谷)

10314 ワード

P 1023税収と補助金問題
この問題は私が1篇の良い問題解の方法を選んだのは不等式を解くことです(出会った最初の不等式を解く問題、もとは最初から解集を無限に定義します)解析は注釈を見てください
#include//             
using namespace std;
const int maxn = 10005;//           

int expect,cost,c,it,scale,sale[maxn];//          (  )    (  )    (    0     )      sale             
double MIN = -1e9,MAX = 1e9;//                    (-1e9 - 1e9) 

int main(){
	
	cin>>expect>>cost>>scale;
	c = cost;
	
	while(cost != -1 && scale != -1){//             0                                    
		sale[cost] = scale;
		for(int i = it + 1;i < cost;i++)
			sale[i] = sale[i - 1] + (scale - sale[it]) / (cost - it);
		it = cost;
		cin>>cost>>scale;
	}
	cin>>cost;//     cost                               
	
	while(sale[it] > cost){//                 cost     0   sale[it + 1]     0 
		it++;
		sale[it] = sale[it - 1] - cost; 
	}//                    (          c      )      it        
	
	for(int i = c;i <= it;i++){
		double ans = (sale[expect] * (expect - c) - sale[i] * (i - c)) * 1.0 / (sale[i] - sale[expect]);//          1.0 !!!!! 
//   ans           
//          : (ans + i - c) * sale[i] <= (ans + expect - c) * sale[expect]; 
		double flag = sale[i] - sale[expect];//               
		if(flag > 0)MAX = min(MAX,ans);//       
		else MIN = max(MIN,ans);//       
	} 
	
	if(MIN > 0)printf("%d",(int)ceil(MIN));//    (ceil)
	else if(MAX < 0)printf("%d",(int)floor(MAX));//    (floor)
	else cout<<'0';//MIN < 0 < MAX
	return 0; 
}