目录

牛客_数组变换_贪心+位运算

题目解析

C++代码1暴力

C++代码2位运算

Java代码位运算

---

牛客_数组变换_贪心+位运算

数组变换__牛客网 (nowcoder.com)

描述：
        牛牛有一个数组，里面的数可能不相等，现在他想把数组变为：所有的数都相等。问是否可行。牛牛可以进行的操作是：将数组中的任意一个数改为这个数的两倍。

这个操作的使用次数不限，也可以不使用，并且可以对同一个位置使用多次。

---

题目解析

如果能够变换成功，那么最大的数除以剩下的数的商，一定都是 2 的 n 次方。

C++代码1暴力

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n = 0, aMax = 0;
    cin >> n;
    vector<int> a(n);
    for(int i = 0 ; i < n; ++i)
    {
        cin >> a[i];
        aMax = max(aMax, a[i]);
    }
    for(int i = 0 ; i < n; ++i)
    {
        while(a[i] < aMax)
        {
            a[i] *= 2;
        }
        if(a[i] > aMax)
        {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

C++代码2位运算

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int n = 0, aMax = 0;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i)
    {
        cin >> a[i];
        aMax = max(aMax, a[i]);
    }
    for(int i = 0 ; i < n; ++i)
    {
        // while(a[i] < aMax)
        // {
        //     a[i] *= 2;
        // }
        // if(a[i] > aMax)
        if((aMax % a[i]) || a[i] != 1 && a[i] < aMax && a[i] & (a[i] - 1) != 0)
        {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

Java代码位运算

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{
    public static void main(String[] args) 
    {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        int b = 0;
        for(int i = 0; i < n; i++)
        {
            arr[i] = in.nextInt();
            b = Math.max(b, arr[i]);
        }
        boolean flag = true;
        for(int i = 0; i < n; i++)
        {
            if(b % arr[i] != 0)
            {
                flag = false;
                break;
            }
            int x = b / arr[i];
            if((x - (x & -x)) != 0)
            {
                flag = false;
                break;
            }
        }

        if(flag) 
            System.out.println("YES");
        else 
            System.out.println("NO");
    }
}