【解题报告】 天才ACM

题目：天才ACM

解题思路：

倍增算法

设p=1，r=l

求出r—r+p这一区间的校验值，如果校验值小于等于t，则r+=p，p*=2；

否则p/=2;

一直重复，直到p等于0的时候，r就是最终答案

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=500005;
long long t,tot;
long long n,m,k;
long long p[maxn];
long long f[maxn];
int l,r,mid,j;
long long min(long long a,long long b)
{
	return a<b? a:b;
}
bool check(int l,int r) 
{
    tot=0;
    long long sum=0;
    for(int i=l;i<=r;i++) 
	f[++tot]=p[i];
    sort(f+1,f+1+tot);
    for(int i=1;i<=m;i++) 
	{
        if (i>=(tot-i+1)) 
		break;
        sum+=(long long)(f[tot-i+1]-f[i])*(f[tot-i+1]-f[i]);
        if(sum>k)
		break;
    }
    if(sum>k)
	return false;
    return true;
}
bool cmp(int x,int y)
{
	return p[x]<p[y];
}
bool calc()
{
	long long sum=0;
	int ll=1,rr=tot;
	for(int i=1;i<=m;i++)
	{
		while(ll<rr&&f[ll]>mid)
		ll++;
		while(ll<rr&&f[rr]>mid)
		rr--;
		if(ll>=rr)
		break;
		sum+=(long long)(p[f[rr]]-p[f[ll]])*(p[f[rr]]-p[f[ll]]);
		if(sum>k)
		break;
		ll++;
		rr--;
	}
	return sum<=k;
}
void work()
{
		cin>>n>>m>>k;
		for(int i=1;i<=n;i++)
		cin>>p[i];
		int ans=0;
		for(int i=1;i<=n;i++)
		{
			for(j=1;i+(1<<j)-1<=n;j++)
			{
				if(!check(i,i+(1<<j)-1))
				break;
			}
			l=i+(1<<(j-1))-1;
			r=min(i+(1<<j)-1,n);
			tot=0;
			for(int k=i;k<=r;k++)
			f[++tot]=k;
			sort(f+1,f+tot+1,cmp);
			while(l<=r)
			{
				mid=(l+r)/2;
				if(calc())
				{
					i=mid;
					l=mid+1;
				}
				else r=mid-1;
			}
			ans++;
		}
		cout<<ans<<endl;
}
int main()
{
	cin>>t;
	while(t--)
	{
		work();
	}
	return 0;
}