普及2 第4题 WA+TLE

常规
1 
#include<bits/stdc++.h>
using namespace std;
long long n,k,a[100010];
int check(int mid){
	int l=1,r=n,ans=0;
	while(l<=r){
		while(a[l]+a[r]>mid)r--;
		ans+=r-l;
		l++;
	}return ans>=k;
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+n+1);
	long long l=0,r=a[n]*2+1;
	while(l+1<r){
		long long mid=(l+r)/2;
		if(check(mid))r=mid;
		else l=mid;
	}cout<<l;
	return 0;
}
2

题面

1 个赞
3

没题目让我们怎么帮你看？

1 个赞
4

image
image757×675 23.7 KB

1 个赞
5

把check里都改为longlong多得10分

2 个赞
6

image
while(l<r)
里面的是while(l<r&&a[l]+a[r]>mid)r–;

2 个赞
7

还有二分是l,r
双指针也是l,r
当然wa

2 个赞
8 
#include<bits/stdc++.h>
using namespace std;
long long n,k,a[100010];
int check(long long mid){
	long long x=1,y=n,ans=0;
	while(x<=y){
		while(x<=y&&a[x]+a[y]>mid)y--;
		ans+=y-x;
		x++;
	}return ans>=k;
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+n+1);
	long long l=0,r=a[n]*2+1;
	while(l+1<r){
		long long mid=(l+r)/2;
		if(check(mid))r=mid;
		else l=mid;
	}cout<<l;
	return 0;
}

还错

1 个赞
9

image
image

x<y!!!

2 个赞
10 
#include<bits/stdc++.h>
using namespace std;
long long n,k,a[100010];
int check(long long mid){
	long long x=1,y=n,ans=0;
	while(x<y){
		while(x<y&&a[x]+a[y]>mid)y--;
		ans+=y-x;
		x++;
	}return ans>=k;
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+n+1);
	long long l=0,r=a[n]*2+1;
	while(l+1<r){
		long long mid=(l+r)/2;
		if(check(mid))r=mid;
		else l=mid;
	}cout<<l;
	return 0;
}
```0  本来还有20
1 个赞
11

格式化一下

3 个赞
12

不知道你二分这样对不对我是这样的
image

3 个赞
13

我试过了改成我这样能过样例你的不能

2 个赞
14 
#include<bits/stdc++.h>
using namespace std;
long long n,k,a[100010];
int check(long long mid){
	long long x=1,y=n,ans=0;
	while(x<=y){
		while(x<=y&&a[x]+a[y]>mid)y--;
		ans+=y-x;
		x++;
	}return ans>=k;
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+n+1);
	long long l=0,r=a[n]*2+1;
	while(l<r){
		long long mid=(l+r)/2;
		if(check(mid))r=mid;
		else l=mid;
	}cout<<r;
	return 0;
}0TLE
1 个赞
15

image
l=mid+1

3 个赞
16

AC谢谢

2 个赞
17

解决方案给自己？

4 个赞
18

给个赞

1 个赞