您的位置: 首页  >  文章  >  10.19 noip 模拟题 【NOIP2018模拟赛2018.10.19】

10.19 noip 模拟题 【NOIP2018模拟赛2018.10.19】

分类: 文章 • 2024-08-04 12:26:10

今天也才改出来一道题orz，大坑最近要填，，，

今天题目难度适中，暴力都打出来了，但是第二题“spfa死了”。

于是今天就改出来了第一题和去练了下dijkstra+堆优化。。。于是时间不够用orz。。

---------------------------------------------------------------------------------------------------------------------------------------------------------------

10.19 noip 模拟题 【NOIP2018模拟赛2018.10.19】

首先我们看到这道题，很容易想到二分一个最大高度，然后枚举每个位置作为x所在地，找能把这个高度两边l，r把它围起来的最大三角形，若所用积木少于m则加高这个最大高度，否则减少。

那么找l，r的时间朴素暴力是O(n^2)的，肯定要T，于是考虑优化：

二分搭建的高度，最低为maxh+1，最高为maxh+sqrt(m)+1

如何在O(n)时间内check呢？

对于搭建积木，我们要搭出一个金字塔形，但是，并不是要搭建整个金字塔形，有时候只要搭建部分即可，如图：

10.19 noip 模拟题 【NOIP2018模拟赛2018.10.19】

首先，要知道的是这道题相对每个i的l是递增的。

我们发现，对于一个位置x，如果能找到它所对的l，那么对于位置x-1，它的l必≤位置x所对的l，且从位置x所对的l ~x-1绝对不满足能做绿色部分的左边框。因为在向左移的过程中，左边的每个位置的h的要求总是增大的（金字塔形）

所以l具有单调性。我们从n到1扫描每个位置，如果当前的l不满足h[l]<h-(i-l)（即不能做绿色部分的左边框），那么我们l--，直到满足要求，然后我们拿一个数组记下每个位置的l

对r也是一样，只要从左往右扫描即可。

我们仅需搭建绿色部分，而不需要搭建蓝色方框内的整个金字塔

如何找到绿色部分呢？

设l为绿色部分的左边界，r为绿色部分的右边界，x为当前要搭建的金字塔顶，h为大金字塔塔高

我们需要在搭建的金字塔所需积木=整个大金字塔所需积木-黄色部分所需积木-紫色部分所需积木-棕色部分所需积木

设黄色部分高为a，则a=h-(x-l)（即图中6-1=5），黄色部分所需积木为a*(a+1)/2。

同理，能算出紫色部分所需积木。

棕色部分所需积木=r前面所有已有积木-l前面所有已有积木。我们想到了什么？前缀和

这样，绿色部分所需积木就算出来了，我们比较它与m的大小关系即可

代码实现：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pt putchar
#define ex pt('\n')
const int MAXN = 1e5 + 5;
int n,m;
int L[MAXN],R[MAXN];
ll h[MAXN],H[MAXN];
ll sum[MAXN];
ll ans = 0;
void in(int &x)
{
	int num = 0,f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1;ch = getchar();}
	while(ch >= '0' && ch <= '9') {num = (num<<3) + (num<<1) + (ch - '0'); ch = getchar();}
	x = num*f;
}
void lin(ll &x)
{
	ll num = 0,f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1;ch = getchar();}
	while(ch >= '0' && ch <= '9') {num = (num<<3) + (num<<1) + (ch - '0'); ch = getchar();}
	x = num*f;
}
void out(int x)
{
	if(x < 0) x = -x,pt('-');
	if(x > 9) out(x/10);
	pt(x%10 + '0');
}

inline void init()
{
	in(n); in(m);
	for(int i = 1;i <= n;i++)
	{
		lin(h[i]); sum[i] = sum[i-1] + h[i];
		ans = max(ans,h[i]);
	}
}

bool check(ll x)
{
	int l = n,r = 1;
	for(int i = n;i >= 1;i--) {while(h[l] < x-(i-l) && l >= 1) l--;L[i] = l;}
	for(int i = 1;i <= n;i++) {while(h[r] < x-(r-i) && r <= n) r++;R[i] = r;}
	for(int i = 1;i <= n;i++)
	{
		if(R[i] == n+1 || L[i] == 0) continue;
		ll a = x - (i - L[i]),b = x - (R[i] - i);
		ll s = x * x - (b + 1) * b/2ll - (a + 1) * a/2ll;
		if(s - (sum[R[i] - 1] - sum[L[i]]) <= m) return 1;
	}
	return false;
}

inline void work()
{
	ll l = ans + 1,r = (ll)(sqrt(m) + 1.00) + ans + 1; 
	while(l < r)
	{
		ll mid = (l + r) >> 1;
		if(check(mid)) l = mid+1;
		else r = mid;
	}
	out(l-1);
}

int main()
{
//	freopen("block.in","r",stdin);
//	freopen("block.out","w",stdout);
	init();
	work();
	return 0;
}

 

相关推荐