刷题记录:牛客NC15052求最值

传送门:牛客

牛客网上的两星题,但是说实话,两星题只是因为这道题的数据出的不是特别好,恰好能被一些奇奇怪怪的特判给巧妙的卡过去了,实际难度应该差不多4星吧

刚开始遇到这道题,显然第一印象是直接暴力啦,当然暴力之前也是应该想到g函数就是一个前缀和的算法,然后试着暴力的解决,下面是我第一次的暴力算法

int a[100005];
int sum[100005];
int main() {
	int n;n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	a[0]=0;sum[0]=0;
	for(int i=1;i<=n;i++) {
		sum[i]=sum[i-1]+a[i];
	}
	int minn=inf;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			if(i==j) continue;
			minn=min((int)(pow(i-j,2)+pow(sum[j]-sum[i],2)),minn);
		}
	}
	cout<<minn<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

然后很不幸的全部暴毙,不出所料的全部Tle,有点难受啊,然后我想了很久没有结果,实在没办法就看了一眼其他人的代码,然后…

int n;
int a[100010];
int main() {
    IOS;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] += a[i - 1];
    }
    int minn = INF;
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n && j <= i + 3; j++) {
            if ((j - i) * (j - i) + (a[j] - a[i]) * (a[j] - a[i]) < minn)
                minn = (j - i) * (j - i) + (a[j] - a[i]) * (a[j] - a[i]);
        }
    }
    cout << minn;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

我TM直接地铁老人问号好吧,这是什么奇奇怪怪的特判方法,不出所料,这肯定不是正解,应该只是数据比较水,怪不得因此只是两星题,显然我是不能直接这么照抄的去解决这个问题的,然后我只能靠自己的小脑瓜继续思考,看着看着我觉得这连个连续的平方似乎有点熟悉啊,这不是就两点之间的距离吗??,似乎突然有了什么思路,但是在我的思想里,即使想到了这一点似乎还是没有什么用,似乎照样是n^2的算法,即不断的比较两点之间的距离,然后我就试着去网上搜一下有什么优化的算法

然后真被我搜到了,这种求两点之间的距离的问题竟然是经典的平面上的最接近点对的题目,并且洛谷上也提供了n(logn)的分治优化算法(如下)

现在的问题就是有n个点,如何求出n个点之间的最短距离

我们先将n个点按照横坐标来进行排序,形成下列这样的分布

然后我们使用分治的思想去优化(重所周知分治是一种巧妙的暴力方式)

我们将n个点分成两组,记为一左一右,

此时我们如果想要求出最接近点对的话有以下三种情况:

1. 最接近点对中的两点都在左边的部分
2. 最接近点对中的两点都在右边的部分
3. 最接近点对中的点对恰好分布在左右两边的部分

对于第一种和第二种情况,在分治的不断进行过程中,我们就可以顺便解决了,具体到代码中

if(l==r) return INF;
if(l==r-1) return dist(l,r)
当我们二分到只剩下一个单独的点时,此时我们为了不干扰答案,将其赋值为无穷大
当我们二分到只有两个点时,此时我们就最近点点对显然就是两点间的距离
1
2
3
4

可能会有人对于为什么上面的代码能解决一二两种情况感到疑惑,下面举一个栗子

假如我们有三个点v,w,x,y,z,我们要求三个点的最接近点对
此时的中间点为x,两边分别为v,w和y,z
此时我们如果是第一种情况或者第二种情况是不是就是被上面的代码解决了,如果点比其多的话,我们照样可以分治到这种情况
1
2
3

然后麻烦就是第三种情况了,对于这一种情况,我们有一个很显然的剪枝方法

因为对于前面的不断分治我们已经求出了两个区间分别的最接近点的距离,如果我们现在要考虑第三种情况的话,显然我们会有以下结论,就是分布在mid左右两边的点,到达mid的横坐标的距离肯定是要比前面我们求出的最接近点的距离都要小的,这样我们才需要考虑

而此时的话,我们就直接选出符合的点即可

选出符合的点之后,再去判断在mid两端两点间的最接近点的距离是否比原来小即可

	for(int i=l;i<=mid;i++) {
		if(!(fabs((point[mid].x-point[i].x)*(point[mid].x-point[i].x))<=min_d)) continue;
		for(int j=mid+1;j<=r;j++) {
			if(!(fabs((point[mid].x-point[j].x)*(point[mid].x-point[j].x))<=min_d)) continue;
			min_d=min(min_d,dist(i,j));
		}
	}
1
2
3
4
5
6
7

然后此时我们就快乐的求出了平面上最接近点的距离啦,洛谷上的这道题,我们就能轻松的解决了

具体代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
struct Point {
	double x,y;
}point[200005];
double dist(int a,int b) {
	return sqrt((point[a].x-point[b].x)*(point[a].x-point[b].x)+(point[a].y-point[b].y)*(point[a].y-point[b].y));
}
double solve(int l,int r) {
	if(l==r) return inf;
	if(l==r-1) return dist(l,r);
	int mid=(l+r)>>1;
	double min_d=min(solve(l,mid),solve(mid+1,r));
	for(int i=l;i<=mid;i++) {
		if(!(fabs(point[mid].x-point[i].x)<=min_d)) continue;
		for(int j=mid+1;j<=r;j++) {
			if(!(fabs(point[mid].x-point[j].x)<=min_d)) continue;
			min_d=min(min_d,dist(i,j));
		}
	}
	return min_d;
}
bool cmp(Point a,Point b) {
	if(a.x == b.x) return a.y < b.y;
	else return a.x < b.x;
}
int main() {
	int n;n=read();
	for(int i=1;i<=n;i++) {
		scanf("%lf%lf",&point[i].x,&point[i].y);
	}
	sort(point+1,point+n+1,cmp);
	double ans =solve(1,n);
	printf("%.4lf",ans);
	return 0;
}
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

但是这道题并没有就这么的结束了,当我们将洛谷上能AC的代码直接改一下交到牛客网上的这道题时,会发现居然被卡了一个点(当然注意要将double改成longlong啦,注意横坐标此时开平方),我直接好家伙,又被卡了一下,十分的难受好吧,仔细的想了一下,似乎之前我们的代码中还漏掉了什么

我们在之前似乎只是优化了横坐标的部分,类比一下是不是纵坐标的部分我们也照样能够优化呢,照着这个思路,我们或许不难的就写出了实际代码:

double solve(int l,int r) {
	if(l==r) return inf;
	if(l==r-1) return dist(l,r);
	int mid=(l+r)>>1;
	double min_d=min(solve(l,mid),solve(mid+1,r));
	for(int i=l;i<=mid;i++) {
		if(!(abs(point[mid].x-point[i].x)<min_d&&abs(point[mid].y-point[i].y)<min_d)) continue;
		for(int j=mid;j<=r;j++) {
			if(!(abs(point[mid].x-point[j].x)<min_d&&abs(point[mid].y-point[j].y)<min_d)) continue;
			if(i==j) continue;
			min_d=min(min_d,dist(i,j));
		}
	}
	return min_d;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

然后发现分数似乎更低了,连洛谷上的那道题竟然都只能的81分了,这是怎么回事呢,当时我百思不得其解,想来想去似乎并没有什么问题,这浪费了我大量时间,最终终于发现了,在之前我们只是关于横坐标进行了排序的操作.那么此时我们的纵坐标肯定是不能以我们的mid来作为标准的,就比如

X                                 
                                  Z


                    mid      
1
2
3
4
5

此时我们即使X离mid超过了mid_d的距离,但是因为Z是在mid上方的,那么此时我们的X与Z之间的距离就不一定是超过我们的mid_d了,此时我们的代码就挂了

那么问题来了,我们究竟该如何的去解决这个问题呢,我们可以先将满足横坐标的点存进一个数组里,在根据纵坐标来排一个序,后来再去枚举我们满足横坐标条件的点去选出能满足纵坐标的点即可

注意下面是因为排序过后的原因,所以J那个部分的判断条件直接放到了循环里面,假设没有拍过序的话,就比如之前我们的代码,会导致循环中途退出!!

具体代码如下:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000001
int n;
struct Point {
	ll x,y;
}point[maxn];
int temp[maxn];
ll pingfang(ll x) {
	return x*x;
}
ll dist(int a,int b) {
	return pingfang(point[a].x-point[b].x)+pingfang(point[a].y-point[b].y);
}
bool cmp(Point a,Point b) {
	if(a.x!=b.x) return a.x<b.x;
	else return a.y<b.y;
}
bool cmp2(int a,int b) {
	return point[a].y<point[b].y;
}
ll solve(int l,int r) {
	if(l==r) return inf;
	if(l+1==r) return dist(l,r);
	int mid=(l+r)>>1;
	ll min_d=min(solve(l,mid),solve(mid+1,r));
	int k=0;
	for(int i=l;i<=r;i++) {
		if(pingfang(point[i].x-point[mid].x)<=min_d) {
			temp[k++]=i;
		}
	}
	sort(temp,temp+k,cmp2);
	for(int i=0;i<k;i++) {
		for(int j=i+1;j<k&&pingfang(point[j].y-point[mid].y)<=min_d;j++) {
			min_d=min(min_d,dist(i,j));
		}
	}
	return min_d;
}
int main() {
	n=read();
	int num;point[0].x=point[0].y=0;
	for(int i=1;i<=n;i++) {
		num=read();
		point[i].x=i;
		point[i].y=point[i-1].y+num;
	}
	ll ans=solve(1,n);
	cout<<ans<<endl;
	return 0;
}
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