首页 前端知识 M 有效算法

M 有效算法

2024-06-01 10:06:01 前端知识 前端哥 535 431 我要收藏

M 有效算法

在这里插入图片描述
本题考验二分知识,思路是二分k的取值,就按第一组样例来说当我们k取值为1的时候我们遍历数组想让|8-x|<=k1的话x的取值范围是7-9,想让|3-x|<=k2的话x的取值范围是1-5,两者x的区间不重合,说明肯定没有x能同时让|8-x|<=k1和|3-x|<=k2,所以不成立,当k=2的时候我们发现每一组x的区间都有重合的地方,那么此时a数组一定是可以全都变成x的,并且当k>2时毫无疑问绝对都可以符合,k的取值是否达标具有单调性,所以可以用二分来枚举。
题解如下:

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define for1 for(int i = 1;i <= n;i++)
#define for0 for(int i = 0;i < n;i++) 
#define forn1 for(int j = 1;j <= n;j++) 
#define forn0 for(int j = 0;j < n;j++) 
#define form1 for (int j = 1; j <= m; j++)
#define form0 for (int j = 0; j < m; j++)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define arrn int* arr = new int[n+2];arr[0] = 0,arr[n+1]=0
#define carr cin >> arr[i]
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define endl '\n'
#define mod  1000000007
#define t() int _; cin >> _; while (_--)
int a[300010];
int b[300010];
int n;
bool cheak(int k)
{
    long long ml = a[1] - 1ll * b[1] * k;
    long long mr = a[1] + 1ll * b[1] * k;
    for (int i = 2; i <= n; i++)
    {
        long long ll = a[i] - 1ll * b[i] * k;
        long long rr = a[i] + 1ll * b[i] * k;
        if (ll > ml)ml = ll;
        if (rr < mr)mr = rr;
    }
    if (mr < ml)return false;
    return true;
}
int main() {
    IOS;
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n;
        for(int i = 1; i <= n; i++)
        cin >> a[i];
        for(int i = 1; i <= n; i++)
        cin >> b[i];
        int l = 0, r = 1e9;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            if (cheak(mid))r = mid-1;
            else l = mid+1;
        }
        cout << l << endl;
    }
    return 0;
}
转载请注明出处或者链接地址:https://www.qianduange.cn//article/10362.html
标签
数据结构
评论
发布的文章

npmjs官网(查询依赖包)

2024-06-07 00:06:56

npx使用及原理

2024-06-07 00:06:36

npm 包管理工具

2024-06-07 00:06:33

vue 思极地图开发

2024-06-07 00:06:28

大家推荐的文章
会员中心 联系我 留言建议 回顶部
复制成功!