前言
这是我的某一门作业题，发出来是对自己的整理，请不要直接搬了，最多给大家提供一个思路而已，肯定还有更优解法。大家可以去探索探索。
正文
n 个人去看电影，本来每人要买一张票，但电影院推出了一个活动：一个身高为 x 的人可以和身高至少为 2x 组合，两人一共只需买一张票。现在给出全体 n个人的身高，请问总共至少要买多少电影票？
输入格式
第一行一个整数 n，代表总人数。
第二行 n 个整数，每个数 A[i]代表每个人的身高。
输出格式
一个整数，表示最少需要购买的电影票数量
数据范围:
1<=n<=500000,1<=A[i]<=100000
样例输入
1 9 7 3 5 5
样例输出
样例解释
1 和 9 配对，7 和 3 配对，剩下 5,5 单独，一共买四张票。
一下子看到这个题，感觉好简单先排序然后一个一个比不就行了嘛，大于两倍的抬走，不够的下一个就行。
但是仔细一想，并不行。
我们要求的是最少的电影票数，这个最少我们如果直接从头比较肯定是不行的。
为了要求买的票最少我们就应该让能搭配的数量越多越好。
比如说你让最小的和最大的搭配，这个是可以搭配成功的，但是就比较浪费了，你让其他大的数字与谁去搭配呢？显然不符合我们的原则。
一共有n个数字，那么最多都搭配成功也就有n/2对了，怎么样能做到呢？看个栗子
若搭配为：1，5，2，5，11，6，则排序后为：1，2，5，5，6，11怎么样能让它达到最多搭配数量呢？当然是1与5，2与6，5与11让第1个数与n/2比较然后大于两倍的抬走，不够换下一个就行。
分析完毕，我们上代码
import java.util.*; public class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); int n = input.nextInt(); int[] N = new int[n]; //vis数组来标记搭配成功的数组 boolean[] vis = new boolean[n]; int num=0; for (int i=0;i N[i]=input.nextInt(); } Arrays.sort(N); int x=n/2; int j=x; for(int i=0;i while(j if((N[i]*2<=N[j])&&!vis[j]&&!vis[i]){ num++; vis[i] = true; vis[j++] = true; break; } } j++; if(j==n) break; } for(int i=0;i if(!vis[i]){ num++; } } System.out.println(num); } }
写完后逻辑上面感觉是没有问题的，信心慢慢去提交但是
没有ac，因为时间复杂度太高了，怎么办呢？肯定得改这个双层循环的地方，如何去掉双层循环？。。。经过我的苦思冥想终于有了答案。
修改后的代码：
import java.util.*; public class Main{ public sta tic void main(String[] args) { Scanner input = new Scanner(System.in); int n = input.nextInt(); int[] N = new int[n]; boolean[] vis = new boolean[n]; int num=0; for (int i=0;i N[i]=input.nextInt(); } Arrays.sort(N); int x=n/2,l=0; while (l < n/2 && x < n) { if (2*N[l] <= N[x]) { vis[l++]=true; vis[x++]=true; num++; } else { x++; } } for(int i=0;i if(!vis[i]){ num++; } } System.out.println(num); } }
也是顺利的ac了
我的总结就是遇到问题不要慌仔细分析是哪里出了问题，然后对症下药即可。
最后，每个人都有自己的思路，肯定还有比这个更优化的解法，欢迎探讨！
