目录
BZOJ1811 mea题解ｃｏｄｅ
BZOJ1811 mea
题目传送门
题解
一道乱搞题目，我们可以设\(s[0]\)为\(x\)，然后我们就可以根据\(m\)数组退出\(s\)数组关于\(x\)的表达式，然后由于\(s\)是非递减的，所以我们可以列\(n\)个不等式，将这些不等式的解集求交之后就是答案的解集，计算一下个数即可。但是似乎BZOJ上这题是挂掉的。只能下数据手测了，至少本机是AC的。。
ｃｏｄｅ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
const int inf=0x7f7f7f7f;
const int maxn=5e6+500;
int n;
int m[maxn];
struct fuc {
int a,b;//ax+b;
}s[maxn];
int Mx,Mn;
/*==================Define Area================*/
void Solve(fuc &A,fuc &B) {
int ret=B.b-A.b;
int div=A.a-B.a;
if(div<0) {
ret/=div;
Mn=max(Mn,ret);
}
else {
ret/=div;
Mx=min(Mx,ret);
}
}
int main() {
read(n);
Mn=-inf;Mx=inf;
for(int i=1;i<=n;i++) {
read(m[i]);
}
s[0].a=1;s[0].b=0;
for(int i=1;i<=n;i++) {
int tot=m[i]*2;
s[i].a=-s[i-1].a;
s[i].b=tot-s[i-1].b;
}
for(int i=0;i<n;i++) {
Solve(s[i],s[i+1]);
}
int ans=max(0,Mx-Mn+1);
printf("%d\n",ans);
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/9439220.html
相关资源：JAVA上百实例源码以及开源项目
