双指针,先上一个超时代码:
#include<iostream>
#include<algorithm>
using namespace std;int t,n;
int e[1001];int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>t;while(t--){//100cin>>n;for(int i=1;i<=n;i++){cin>>e[i];}sort(e+1,e+n+1);int ans=0;int a,b;for(int i=1;i<(n-1);i++){//1000-3a=i+1;b=a+1;
// cout<<"i:"<<i<<endl;
// cout<<"a1:"<<a<<endl;
// cout<<"b1:"<<b<<endl;while(a<n){//1000-2int tag=0;b=a+1;while((e[i]+e[a])>e[b]){if(b<n) {b++;tag++;//cout<<"tag:"<<tag<<endl;}else{
// cout<<"a3:"<<a<<endl;
// cout<<"b3:"<<b<<endl;if((a+1)==b){ans=ans+b-a;}else{tag++;}//ans=ans+b-a;break;}
// cout<<"a2:"<<a<<endl;
// cout<<"b2:"<<b<<endl;}if((a+1)<b){ans=ans+tag;}//ans=ans+b-a-1;a++;//cout<<"ans:"<<ans<<endl;//cout<<"a:"<<a<<endl;}}cout<<ans<<endl;}
}
accept代码:
#include<iostream>
#include<algorithm>
using namespace std;int t,n;
int e[1001];int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>t;while(t--){//100cin>>n;for(int i=1;i<=n;i++){cin>>e[i];}sort(e+1,e+n+1);int ans=0;int a,b;for(int i=3;i<=n;i++){a=1;b=i-1;while(a<b){if(e[a]+e[b]>e[i]){ans=ans+b-a;b--;}else a++;}}cout<<ans<<endl;}
}