专题一 B_牛客博客

题目链接

https://codeforces.com/contest/91/problem/B

思路

二分，单调性

题目大意：

给定一个数组

定义每一个数的不满度为：在这个数后面的离他最远的比这个数小的数之间的距离。

数据范围为1e5

暴力来看，直接遍历循环查找为 $O (N^{2})$ 的时间复杂度，所以需要优化

直接正面从前往后查找是没有其他手段了，所以我们尝试后面找起

从末尾开始，每次将末尾数值加入新数组中，

我们可以发现这里其实是具有单调性的，当每次加末尾数值加入后，我们发现在你之前加入的数中如果有比你小的话，那么这个数绝对无法用到的，即比你更加小而且更后面，所以当遍历的数大于前一个时，没有必要加入数组中。只要保证了这个新数组具有了递减性质，具有了单调性。

那么当我们为当前的数查找比他小而且离他最后面的数时可以利用前面的单调性，进行二分查找

将 $O (N)$ 的查找优化为 $O (l o g n)$ 这样总的时间复杂度就变为了 $O (N l o g n)$ 在 1e5的时间复杂度是可以过的。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
const int N = 100010;
typedef long long ll;
int p[N];//原数组
int l[N];//答案数组
int k[N];//判断数组，判断是否存在比他小而且比他后面的数存在
vector<int> s;//来存储单调队列
map<int,int> ma;//map来存下每个数的下标
int n;
/*重点 每次二分调了半死
*/
int binary(int res)
{
    int l = 0;
    int r = s.size()-1;
    //我们的答案数组是递减的，我们要找到的是<res的最大值
    while(l<r)
    {
        int mid = (l+r)>>1;
        if(s[mid] >=res) l = mid+1 ;//大于res则左边界向右，缩小值域
        else r = mid;//大于则向右缩小值域
    }
    return ma[s[l]];//返回该下标对应的值在map上的下标
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);//关流操作
    cin>>n;
    for(int i = 1;i<=n;i++)//输入与记录
    {
        cin>>p[i];
        ma[p[i]] = i;
    }
    
    int ls = p[n];//初始的单调队列头
     s.push_back(p[n]);//进入数组
     k[n] = 1;//最后一个数绝对没有符合条件的数
    for(int i = n-1;i>=1;i--)
    {
        //判断如果这个数小于当前数组的最小值，那么他是找不到的，并且更新数组
        if(p[i]<=ls)
        {
            k[i] = 1;
           l[i] = p[i];
           ls = p[i];
           s.push_back(p[i]);
        }
        else
        {
             int ans = binary(p[i]);//大于当前数组最小值，可以进行二分查找
             l[i] = ans - i -1;
        }
    }
     for(int i =1;i<=n;i++)
    {
        if(k[i]==1) cout<<"-1 ";
        else cout<<l[i]<<" ";
    }
    return 0;
}