题解：P8244 [COCI2013-2014#3] KOLINJE

题目传送门

转化一下题意，可得：我们要找到一个数

k

，使得其满足

n-1

个不等式：

\sum_{i=1}^{n-1} a_i+b_{i}\times k \geq a_{i+1} +b_{i+1} \times k

移一下项：

\sum_{i=1}^{n-1} a_i-a_{i+1} \geq (b_{i+1} - b_i)\times k

可以发现，我们只需要把每一个不等式处理出来，取并集就是

k

的解集；

又因他要最小的，取下界即可；

考虑如何解一个不等式：

$b_{i+1} - b_i > 0$ ，有 $k \le \frac{a_i-a_{i+1}}{b_{i+1} - b_i}$
$b_{i+1} - b_i < 0$ ,有 $k \ge \frac{a_i-a_{i+1}}{b_{i+1} - b_i}$
$b_{i+1} - b_i = 0$ ,有 $a_i-a_{i+1} \ge 0$

（其实就是模拟解不等式的过程）

注意事项：

精度问题；

一定要考虑 $b_{i+1} - b_i = 0$ 的情况；

像解不等式组，也有上界小于下界的情况，无解；

最后的答案是 $k\times \sum_{i=1}^n b_i$ ;

code

CPP

#include <bits/stdc++.h>//万能头文件
using namespace std;
inline long long read(){//快读
	long long x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=1e3+5;
int n;
int a[N],b[N];
int da[N],db[N];
int32_t main(){
//	ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
//	freopen("huo.in","r",stdin);
//	freopen("huo.out","w",stdout);
	n=read();
	long double sum=0;
	long double L=0,R=1e9;
	for(int i=1;i<=n;i++)a[i]=read(),b[i]=read(),sum+=b[i];
	for(int i=1;i<n;i++){
		da[i]=a[i]-a[i+1];
		db[i]=b[i+1]-b[i];
		if(db[i]>0){
			R=min(R,(long double)da[i]/db[i]);
		}else if(db[i]<0){
			L=max(L,(long double)da[i]/db[i]);
		}else{
			if(da[i]<0)return puts("-1"),0;
		}
	}
	if(R<L)return puts("-1"),0;
	cout<<fixed << setprecision(12) << L*sum;
	return 0;
}

完结撒花

题解：P8244 [COCI2013-2014#3] KOLINJE

文章操作

题目传送门

相关推荐

评论

题解：P8244 [COCI2013-2014#3] KOLINJE