洛谷原题链接 || Hydro 域原题链接。
此题相当于能不能找到 4 个数，让它们和为 m。
思路1
暴力枚举 4 个数，然后求和。
如果和为 m,输出 Yes 并返回。
结尾输出 No。
复杂度 O(n^4)。
代码1
#include <bits/stdc++.h>
using namespace std;
int main() {
int n,a[5010],m;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n-3;i++)
for(int j=i+1;j<=n-2;j++)
for(int k=j+1;k<=n-1;k++)
for(int l=k+1;l<=n;l++)
if(a[i]+a[j]+a[k]+a[l]==m){
cout<<"Yes";
return 0;
}
cout<<"No";
return 0;
}
思路2
我们考虑二分优化。
先将数组排序。
我们考虑只枚举 2 个数，二分另外两个数出现的位置。
如果和为 m，输出 Yes 并返回。
结尾输出 No。
复杂度 O(n^2 \log n)。
代码2
#include<bits/stdc++.h>
using namespace std;
int n,a[5005],t;
int main(){
cin>>n>>t;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1);
for(int i=1;i<n-2;i++){
for(int j=i+1;j<=n-2;j++){
int l=j+1,r=n;
while(l<r){
int mid=(l+r)/2;
if(a[i]+a[j]+a[l]+a[r]==t){
cout<<"Yes";
return 0;
}
else if(a[i]+a[j]+a[l]+a[r]<t)l=mid+1;
else r=mid-1;
}
}
}
cout<<"No";
return 0;
}
