F 阿宁的二进制 如果用sort+插排可以过吗？

我的思路是先进行一次快排

然后for循环计算每次操作的值到新数组（如果为1，记录最大操作次数跳出循环）

因为每次操作最大数值改了，所以要对a[]重新排序。

但因为数组只有一个位置是无序的，所以插入排序一次循环就行（其实是两次，但O(n)=n）

最后判断k值，大于最大操作次数就输出1，否则输出新数组保存的值就行

但是他报超时啊！！！

但是他报超时啊！！！

但是他报超时啊！！！

不能用插入排序吗？

#include <bits/stdc++.h>
using namespace std;

int count1(int n) {
	int count = 0;
	while (n > 0) {
		if (n & 1 == 1)
			count++;
		n = n >> 1;
	}
	return count;
}

void insert_sort(int a[], int n, int flag) {
	int fl;
	for (int i = 0; i < n; i++) {
		if (a[i] > flag) {
			fl = i;
			break;
		}
	}

	for (int i = n - 1; i > fl ; i--) {
		a[i] = a[i - 1];
	}
	a[fl] = flag;
}


int main() {
	int n, q, a[200005], k, r[200005], f;
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	for (int i = 1;i<1000000000; i++) {
		a[n - 1] = count1(a[n - 1]);
		r[i] = a[n - 2];
		insert_sort(a, n, a[n - 1]);
		if (r[i] == 1) {
			f = i;
			break;
		}
//		cout << r[i] << " ";
	}
//	cout << endl;


	for (int i = 0; i < q; i++) {
		cin >> k;
		if (k < f) {
			cout << r[k];
		} else {
			cout << "1";
		}
		if (i != q - 1) {
			cout << endl;
		}
	}
}