c++题目_T307715 风之循环

题目背景

第十五届东方人气投票 音乐部门 317名

第四次国内不知道东方的人对东方原曲的投票调查 83名

题目描述

既然射命丸文的那个问题一秒钟就被看穿了，那么她只好去取材了。

在山上路遇河童的时候，她看到河城荷取为了造计算机，正在解决一个小问题。这个问题如下：

给定一个序列AA，请问在这个序列中，两个数之间的最大距离是多少。

文文看到了大新闻的迹象，于是就仔细打听了数字之间的距离的定义。河童说两个数字之间的距离定义就是：把两个数都转化为二进制，对应每一位上的0101数字之差之和。

例如：66用二进制表示是(110)2(110)2​，而55用二进制表示是(101)2(101)2​，所以66和55的距离是22

文文把这个问题给了你，让你求解这个问题，因为她还要在舆论上对付大狸子去。

输入格式

第一行输入一个nn，表示序列的长度

第二行输入nn个数字，表示这个序列A1⋯AnA1​⋯An​

输出格式

输出一个数字，表示这个序列中的最大距离

输入输出样例

输入 #1复制

3
2 3 4

输出 #1复制

3

说明/提示

对于10%的数据，n=2n=2

对于20%的数据，n≤4n≤4

对于所有的的数据，2≤n≤10002≤n≤1000，1≤1≤序列中任何一个数字 ≤10000000000≤10000000000

代码：

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

int maxDistance(vector<int>& nums) {
    int n = nums.size();
    int maxDist = 0;

    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            int num1 = nums[i];
            int num2 = nums[j];
            int diffSum = 0;

            while (num1 > 0 || num2 > 0) {
                int bit1 = num1 & 1;
                int bit2 = num2 & 1;
                if (bit1 != bit2) {
                    diffSum++;
                }
                num1 >>= 1;
                num2 >>= 1;
            }

            maxDist = max(maxDist, diffSum);
        }
    }

    return maxDist;
}

int main() {
    int n;
    cin >> n;

    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    int maxDist = maxDistance(nums);

    cout << maxDist << endl;

    return 0;
}