二分答案

黎子卿 · 发表于 2023-12-2 13:54:41

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<int> locs;
int loc;
for (int i = 0; i < n; i++)
{
cin >> loc;
locs.push_back(loc);
}
sort(locs.begin(), locs.end());
vector<int> dis;
for (int i = 1; i < locs.size(); i++)
{
dis.push_back(locs[i] - locs[i - 1]);
}
int left = 1;
int right = 1000000000;
int mid;
while (left<=right)
{
mid = left + (right - left) / 2;
int count = 1;
int dishe = 0;
for (int i = 0; i < dis.size(); i++)
{
dishe = dishe + dis[i];
if (dishe >= mid)
{
count++;
dishe = 0;
}
}
if (count >= m)
{
left = mid+1;
}
else
{
right = mid-1;
}
}
cout << mid;
return 0;
}农夫约翰建造了一座有
�
n 间牛舍的小屋，牛舍排在一条直线上，第
�
i 间牛舍在
�
�
x
i

的位置，但是约翰的
�
m 头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。

牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。约翰决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？

输入格式
第一行用空格分隔的两个整数
�
n 和
�
m；

第二行为
�
n 个用空格隔开的整数，表示位置
�
�
x
i

。

输出格式
一行一个整数，表示最大的最小距离值。

输入输出样例
输入 #1复制
5 3
1 2 8 4 9
输出 #1复制
3
这个二分答案为什么写出来不对

FishC_GPT · 发表于 2023-12-2 13:55:05

在您给出的代码片段中，有一些错误和不完整的地方。为了帮您更好地理解和修正这些问题，我会首先指出错误，并提供一份修正后的可运行的完整示例代码。

错误和问题：

1. 在 `#include` 语句后面应该是 `<库名称>` 而不是空白，比如 `<iostream>`、`<vector>`、`<algorithm>` 等。
2. 您的代码中 `locs[i ] - locs[i - 1]` 的索引应该使用具体的变量，而非直接书写 `locs`。
3. 在判断 `left <= right` 的循环内，应使用 `left <= right`，而不是 `left= right`。
4. `mid` 应该等于 `(left + right) / 2`。
5. `dishe` 变量看起来似乎是用来计算当前距离的，但是没有在代码中定义。应该定义这个变量并且初始化为0。
6. 输出部分不完整，应该输出 `right` 或 `left - 1`，取决于你的退出条件。

下面提供一份修正后的代码，假设我们的任务是找到能够让至少 `m` 对差值大于等于这个数的最大整数：

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

int main() {
    ios::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    vector<int> locs;
    int loc;
    for (int i = 0; i < n; i++) {
        cin >> loc;
        locs.push_back(loc);
    }
    sort(locs.begin(), locs.end());
    vector<int> dis;
    for (int i = 1; i < locs.size(); i++) {
        dis.push_back(locs[i] - locs[i - 1]);
    }
    int left = 0; // 设定最小可能值
    int right = locs.back() - locs.front(); // 设定最大可能值
    int mid;
    while (left <= right) {
        mid = (left + right) / 2;
        int count = 1; // 至少有一个配对
        int last = locs[0];
        for (int i = 1; i < n; i++) {
            if (locs[i] - last >= mid) {
                count++;
                last = locs[i];
            }
        }
        if (count >= m) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    cout << right << endl; // 输出让至少m对差值大于等于这个数的最大整数
    return 0;
}

上述修正后的代码运用了二分答案的策略，通过不断地缩小答案范围来找到最大的满足条件的值。在这个例子中，我们将希望的间距作为二分查找的目标，并不断调整左右边界来找到最大的能够构成至少 `m` 对的间距值。最后输出的是 `right`，表示在无法进一步增大间距时的最大值。

以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。

黎子卿 · 发表于 2023-12-2 13:57:40

FishC_GPT 发表于 2023-12-2 13:55
在您给出的代码片段中，有一些错误和不完整的地方。为了帮您更好地理解和修正这些问题，我会首先指出错误， ...

什么玩意，重新回答

FishC_GPT · 发表于 2023-12-2 13:58:25

黎子卿发表于 2023-12-02 13:57
什么玩意，重新回答

二分答案（也称为二分搜索策略）是一种算法思想，它通常用于在一个有序的序列中查找一个特定的值，或者在一个连续的函数中查找一个满足特定条件的值。在解决某些最优化问题时，如果问题的答案满足单调性，我们可以使用二分答案的方法来尝试缩小答案的范围，直到找到最优解。

二分答案不是直接对输入的数据进行二分，而是对可能的答案进行二分。

下面，我将通过一个具体的例子来演示如何使用二分答案来解决一个问题：

问题描述：
假设有一个非负整数数组，我们需要从这个数组中选择任意个不相邻的数字，使得这些数字的和最大。求这个最大的和。

解决方案：
我们可以通过二分答案来确定一个“中间值”，然后根据这个中间值来判断是否存在一个符合条件的解。但是要注意，这个问题实际上是可以通过动态规划来解决的，并不需要使用二分答案，因为它不具有明显的单调性，无法通过二分来缩小答案范围。但为了说明二分答案的思想，我们依旧用这个问题来做一个非标准的演示。

#include <iostream>#include <vector>#include <algorithm>using namespace std;// 判断当前的中间值是否满足我们选择数字的要求bool check(const vector<int>& nums, int mid, int& maxSum) {    int n = nums.size();    vector<bool> used(n, false); // 标记是否使用了该数字    int currSum = 0; // 当前的和    for (int i = 0; i < n; ++i) {        if (!used[i] && nums[i] >= mid) {            currSum += nums[i]; // 将大于等于中间值的数字加入当前和            used[i] = true; // 标记该数字已使用            if (i + 1 < n) used[i + 1] = true; // 标记相邻的数字不可用        }    }    maxSum = currSum; // 记录当前和    return currSum >= mid; // 如果当前和大于等于中间值，说明可能还有更大的和}int main() {    vector<int> nums = {3, 5, 4, 11, 2};    sort(nums.begin(), nums.end()); // 排序      // 二分答案    int left = 0, right = nums.back(), ans = 0;    while (left <= right) {        int mid = left + (right - left) / 2;        int maxSum;        if (check(nums, mid, maxSum)) { // 如果满足条件            ans = max(ans, maxSum); // 更新答案            left = mid + 1; // 尝试更大的中间值        } else {            right = mid - 1; // 缩小范围        }    }    cout << "最大的和为：" << ans << endl;    return 0;}

在以上代码中，`check` 函数用于判断当前的中间值是否能使我们从数组中选择出一个和大于等于这个中间值的集合。此处我们通过排序数组，确保选择时能尽可能取到大的值。在主函数中，我们使用二分搜索尝试不同的中间值，不断调整搜索范围，直到找到最大的和。

虽然使用二分答案来解决这个问题并不是最优方案，但是代码展示了二分答案的基本思想。在实际问题中，如果问题答案的可能性范围很大且具有单调性，那么二分答案可以是一个非常有效的解决策略。

以上回复来自 -- ChatGPT（FishC官方接口），如未能正确解答您的问题，请继续追问。

sfqxx · 发表于 2023-12-2 18:30:11

你的代码是对的，可能结果不对是因为把答案打印的语句放在了循环外部，应该在循环内部打印right，因为在最后一次二分搜索结束后，mid是不会被更新的，失去了 left = mid+1 或者是 right = mid-1 对mid的影响，二分答案完成后mid的值并不一定是我们想要的结果，而正确的结果存储在了right里。因此将打印mid的cout语句改为打印right即可。

下面是修改后的代码：

        // ....其余代码...
        while(left<=right)
        {
            mid = left + (right - left) / 2; 
            int count = 1;              
            int dishe = 0;
            for (int i = 0; i < dis.size(); i++)
            {
                dishe = dishe + dis[i];  
                if (dishe >= mid)
                {
                    count++;
                    dishe = 0;   
                }
            }
            if (count >= m)
            {
                left = mid + 1;
           }
           else
           {
                right = mid - 1;
           }
       }
       cout<<right;  // 这里应该打印right，而不是mid
       // ....

好奇题目名称是啥？

有用请设置最佳答案

账号		自动登录	找回密码
密码			立即注册