16981等腰三角形

16981等腰三角形

⭐️难度：中等 🌟考点：双指针、贪心 📖

📚

import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n=in.nextInt(); int a[]=new int[n],b[]=new int[n]; for(int i=0;i<n;i++) a[i]=in.nextInt(); for(int i=0;i<n;i++)b[i]=in.nextInt(); Arrays.sort(a); Arrays.sort(b); int ans=0; for(int i=0,j=0;i<n;i++){ if(2*a[i]>b[j]){ ans++; j++; } } System.out.println(ans); } }

利用贪心思想，把两个数组排序（短的跟短的配，长的跟长的配），利用双指针，验证两个指针所指的长度能否拼成一个三角形（三角形两边之和大于第三边），可以的话就两个指针都前进，不能的话指向等腰边的指针前进。 验证是否构成三角形时，不用验证一条等腰边与另一条边之和是否大于另一条等腰边，因为一定是大于的，所以只需要验证两条等腰边是否比另一条边长。