题目传送门
题意
本题的意思就是在一堆木棒中找出三根木棒且这三根木棒可以围成一个三角形（较短的两根木棍长度和大于最长的那根木棍长度）。
思路
一开始我想到的是用搜索，枚举所有的方式。
20分 Code
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
| #include<bits/stdc++.h>
using namespace std;
int a[8005],ans[10];
int n;
int a_cnt=0;
bool check(int a,int b,int c){
if(a+b>c&&a+c>b&&b+c>a&&abs(a-b)<c&&abs(a-c)<b&&abs(b-c)<a)return 1;
return 0;
}
void dfs(int p,int cnt){
if(cnt>3){
if(check(ans[1],ans[2],ans[3])){
a_cnt++;
}
return ;
}
if(p>n){
return ;
}
dfs(p+1,cnt);
ans[cnt]=a[p];
dfs(p+1,cnt+1);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
dfs(1,1);
cout<<a_cnt;
return 0;
}
|
只有20分。
所以我想到了使用双指针，双指针法：对于每个木棍 $a_i$ ，我们将其作为最长的那根木棍，然后使用双指针法在 $a_0$ 到 $a_{i-1}$ 之间找到满足 $a_j + a_k > a_i$ 的 $j$ 和 $k$ 。
AC Code
接下来就献出本蒟蒻的代码吧。
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
| #include<bits/stdc++.h>
using namespace std;
int a[8005];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++) {
cin>>a[i];
}
sort(a+1,a+1+n);
long long ans=0;
for (int i=n;i>=3;i--){
int l=1;
int r=i-1;
while (l<r) {
if (a[l]+a[r]>a[i]) {
ans+=r-l;
r--;
} else {
l++;
}
}
}
cout<<ans;
return 0;
}
|