程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> acd - 1427 - Nice Sequence(線段樹)

acd - 1427 - Nice Sequence(線段樹)

編輯:C++入門知識

acd - 1427 - Nice Sequence(線段樹)


題意:一個由n個數組成的序列(序列元素的范圍是[0, n]),求最長前綴 j ,使得在這個前綴 j 中對於任意的數 i1 < i2,都滿足任意的 m <= j,i1 在前 m 個數裡出現的次數 >= i2 在前 m 個數裡出現的次數 - k (1 ≤ n ≤ 200 000, 0 ≤ k ≤ 200 000)。

 

——>>第一個前綴 j 不滿足,那麼後面的前綴一定不滿足(因為前綴 j 不滿足)。。所以,從左往右掃描,每次取所有數字 i 的最少出現次數與當前掃描到的數出現的次數比較看是否滿足條件即可。。

所有數字 i 指的是哪些數字呢?是已經出現過的數嗎?樣例2說明不是。。是不大於當前出現過的最大整數嗎?WA告訴我不是。。而是 <= a[j] 的所有非負整數。。

所有數字 i 出現次數的最小值,我想到了RMQ和線段樹,最後選了線段樹來維護這個最小值。。

 

#include 
#include 
#include 

#define lc (o << 1)
#define rc ((o << 1) | 1)

using std::min;
using std::max;

const int MAXN = 200000 + 10;
const int INF = 0x3f3f3f3f;

int n, k, Max;
int minv[MAXN << 2], cnt[MAXN];
int a[MAXN];

void Read()
{
    Max = -1;
    for (int i = 1; i <= n; ++i)
    {
        scanf(%d, a + i);
        ++a[i];
        if (a[i] > Max)
        {
            Max = a[i];
        }
    }
}

void Build(int o, int L, int R)
{
    minv[o] = 0;
    if (L == R) return;
    int M = (L + R) >> 1;
    Build(lc, L, M);
    Build(rc, M + 1, R);
}

void Update(int o, int L, int R, int q)
{
    if (L == R)
    {
        minv[o] = cnt[q];
        return;
    }
    int M = (L + R) >> 1;
    if (q <= M) Update(lc, L, M, q);
    else Update(rc, M + 1, R, q);
    minv[o] = min(minv[lc], minv[rc]);
}

int Query(int o, int L, int R, int ql, int qr)
{
    if (ql <= L && R <= qr)
    {
        return minv[o];
    }
    int ret = INF;
    int M = (L + R) >> 1;
    if (ql <= M) ret = min(ret, Query(lc, L, M, ql, qr));
    if (qr > M) ret= min(ret, Query(rc, M + 1, R, ql, qr));

    return ret;
}

void Solve()
{
    int i;

    memset(cnt, 0, sizeof(cnt));
    for (i = 1; i <= n; ++i)
    {
        ++cnt[a[i]];
        Update(1, 1, Max, a[i]);
        if (Query(1, 1, Max, 1, a[i]) < cnt[a[i]] - k) break;
    }
    printf(%d
, i - 1);
}

int main()
{
    while (scanf(%d%d, &n, &k) == 2)
    {
        Read();
        Build(1, 1, Max);
        Solve();
    }

    return 0;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved