【JZOJ A组】【NOIP2017提高A组模拟7.10】随机
程序员文章站
2022-03-31 19:10:37
...
题目
思路
水法
正解时不可能的,这辈子都不可能的
首先,我们发现选两个端点作为si,sj才是最优的。
所以我们可以枚举区间长度(i
#include<cstdio>
#include<cmath>
using namespace std;
int ans,n,a[1000077];
int main()
{
freopen("random.in","r",stdin);
freopen("random.out","w",stdout);
scanf("%d",&n);
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
ans=n;
for(int i=2; i<ans; i++)
{
for(int j=1; j+i<n; j++)
{
if(abs(a[j]-a[j+i-1])<ans) ans=abs(a[j]-a[j+i-1]);
}
}
printf("%d",(ans>1?ans:2));
}
正解
啊,真香!
问题是,怎么维护?
我们可以开两个set,一个记录a[l..r] (s),一个记录(s1-s0,s2-s1…) (ss)
首先考虑加入一个数x。
设x在s中的位置为t,可以发现我们要把SS(St+1-St-1)删掉,再插入与其相邻的两个数。
然后考虑删除一个数x
与插入反过来,删掉相邻两个,插入一个。
我的程序玄学WA,但当个伪代码是可以的
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<set>
using namespace std;
const int maxn=1000077,inf=0x3f3f3f3f;
multiset<int> s,ss;
int n,a[maxn],ans;
int main()
{
// freopen("random.in","r",stdin);
// freopen("random.out","w",stdout);
scanf("%d",&n);
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
int l=1,r=2;
s.insert(a[1]); s.insert(a[2]); ss.insert(abs(a[1]-a[2]));
ans=inf;
multiset<int>::iterator si,ssi=ss.begin();
while(r<=n&&l<r)
{
int t=*ssi,t1=r-l+1;
ans=min(ans,max(t,t1));
if(t>t1)
{
r++;
s.insert(a[r]);
si=s.find(a[r]);
int x=*--si; si++; int y=*++si; si--;
ss.erase(abs(x-y));
ss.insert(abs(*si-*--si)); ss.insert(abs(*++si-*++si));
}else
{
si=s.find(a[l]);
ss.erase(abs(*si-*--si)); ss.erase(abs(*++si-*++si));
int x=*si; si--; si--; int y=*si;
ss.insert(abs(x-y));
s.erase(a[l]); l++;
}
}
printf("%d",ans);
}
上一篇: php5.3.10自动化部署脚本第一版_PHP教程
下一篇: 水滴融合效果
推荐阅读
-
JZOJ5397. 【NOIP2017提高A组模拟10.6】Biology
-
JZOJ6893. 【提高组模拟】小 T 与灵石(stone)题解
-
JZOJ 5820. 【NOIP提高A组模拟2018.8.16】 非法输入
-
JZOJ5822 【NOIP提高A组模拟2018.8.16】 量子纠缠
-
JZOJ 5395. 【NOIP2017提高A组模拟10.6】Count
-
100043. 【NOIP2017提高A组模拟7.13】第K小数
-
JZOJ6893. 【提高组模拟】小 T 与灵石(stone)题解
-
【JZOJ A组】【NOIP2017提高A组模拟7.10】随机
-
【JZOJ A组】【NOIP2017提高A组模拟7.10】区间
-
【jzoj5285】【NOIP提高组模拟赛A组8.16】【排序】