每日OJ题_牛客_数组变换_贪心+位运算_C++_Java

目录

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

题目解析

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");}
}