题目询问将一组数变成一半为平方数,一半为非平方数 的最少步数。
初始化所有的平方值,注意要开到比1e9大的第一个数。
然后读取,把所有值与其最近的平方数(lower_bound)之差push到一个优先队列里。
并统计平方数的个数S 和0的个数Z(因为0需要改变两次才能到一个非平方数)。
然后根据S和Z判断输出,详见代码。
#include <bits/stdc++.h>
using namespace std ;
typedef long long LL;typedef long long ll ;
int arr[50000] ;int init(){int n = 0 , i = 0;while(n * n <= 1e9){arr[i ++] = n * n ;n ++ ;}arr[i++] = n * n ;return i ;
}
const int maxn = 200005 ;
int s[maxn] ;
priority_queue<int , vector<int> , greater<int> > pq ;
int main(){int len = init() ;int n , temp ;while(~ scanf("%d" , &n)){while(!pq.empty()) pq.pop() ;int sqnum = 0 ,zeronum = 0 ;for(int