2021阿里笔试题

大家好，又见面了，我是你们的朋友全栈君。

n个人，初始序号为a[i]，当某个人的序号是某个整数的平方时，则获胜。现在发放一定数量的券，每张券可以是自己的序号加一或减一。求让一半的人获胜至少需要多少张券。

// testali.cpp : 定义控制台应用程序的入口点。
//

#include “stdafx.h”
#include <math.h>
#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{

    
    int n ;
    cin >> n;
    int *a =new int[n];
    int i =0;
    
    while(i<n){

        
    cin>>a[i++];

    }
    int ans = 0;
    
    //第一步：遍历数组所有成员，求出每一个数据使用的最少券数，记录到原数组中，之后从小到大排序，取一半的人数

    for (int i =0;i <n;i++)
    {

        double c = sqrt((double)a[i]);

        int tmp = (int) c;
        //cout<< “c== ” <<c <</* endl;
        //cout<<“tmp == ” << tmp << endl;*/

        if(tmp*tmp != a[i])
        {

            //求得每一个数据的最少使用券数量
            a[i]= min((tmp+1)*(tmp+1)-a[i],a[i]-tmp*tmp);

        }
        else{

            a[i]=0;
        }
    }
    sort(a, a+n);
    for(int i =0;i <n/2;i++)
    {    
        ans+=a[i];
    }
    cout<< “ans == ” << ans<< endl;
    cout<< endl;
    system(“pause”);
    return 0;
}