此题用枚举两个数和来找另外两个数，注意4个数各不相同，所以要把下标也存入数组，用不定长数组vector比较好
#include<algorithm> #include<iostream> #include<vector> using namespace std; typedef pair<int, int> P; vector<P>ans[200001]; int main() { ios::sync_with_stdio(false); int a[1001], n, s, cnt = 0; cin >> n >> s; for (int i = 0; i < n; i++) cin >> a[i]; sort(a, a + n); for (int i = 0; i < n - 1; i++) for (int j = i + 1; j < n; j++) ans[a[i] + a[j]].push_back({ i,j }); for (int i = 0; i<n - 1; i++) for (int j = i + 1; j < n; j++) { int x = s - a[i] - a[j]; if (x <= 0) continue; cnt += ans[x].end() - lower_bound(begin(ans[x]), end(ans[x]), P(j, n));//所有数下标小于n //由于pair排序规则是先比第一个，第一个相同再比第二个 //所以此lower_bound返回第一个大于等于P(j,n)的元素，可保证下标不重复 } cout << cnt << endl; }
来自渣渣的一点提示 “其中的数各不相同” “每行一个正整数(小于10^5)” 暗示用数组保存，某个数是否出现过 为防重复算先排序 最后看程序注释处优化
using namespace std; int n,s; int cnt[100010]; vector V; int main() { cin>>n>>s; int ans=0; for(int i=1;i<=n;i++) { int xx;cin>>xx; V.push_back(xx); cnt[xx]=1; } sort(V.begin(),V.end()); for(int i=0;i<V.size();i++) for(int j=i+1;j=V[j+1]+V[j+2]) //预先判断是否太大 for(int k=j+1;kV[k] && cnt[p]) ans++; } cout<<ans<<endl; return 0; }
此题用枚举两个数和来找另外两个数，注意4个数各不相同，所以要把下标也存入数组，用不定长数组vector比较好
来自渣渣的一点提示
“其中的数各不相同” “每行一个正整数(小于10^5)”
暗示用数组保存，某个数是否出现过
为防重复算先排序
最后看程序注释处优化
include
using namespace std;
int n,s;
int cnt[100010];
vector V;
int main()
{
cin>>n>>s;
int ans=0;
for(int i=1;i<=n;i++)
{
int xx;cin>>xx;
V.push_back(xx);
cnt[xx]=1;
}
sort(V.begin(),V.end());
for(int i=0;i<V.size();i++)
for(int j=i+1;j=V[j+1]+V[j+2]) //预先判断是否太大
for(int k=j+1;kV[k] && cnt[p]) ans++;
}
cout<<ans<<endl;
return 0;
}