hihocoder offer收割编程练习赛10 C 区间价值

思路：

令v[l, r](0<= l <= r < n)表示区间[l,r]的价值，则长度为n的区间的价值最少为0，最多为n*(n-1)/2。整体对价值二分，求能满足sum{v[l, r](0<= l <= r < n) <= val} >= k的最小的val即为第k小的区间价值。

在统计满足条件的区间个数的时候，可以用动态规划，令dp[i]表示v[0, i]，则

dp[i+1] = dp[i] + {0~i-1位置a[i]出现的次数}，再利用尺取法在迭代的过程中累加价值不超过val的区间个数。

还可用离散化的技巧预处理，将数据范围压缩到0~n-1。

时间复杂度O(n*log(n))。

实现：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <map>

 #include <algorithm>

 using namespace std;

 typedef long long ll;

 const ll INF = 0x3f3f3f3f3f3f3f3f;

 int t, n, k, a[], num[];

 map<int, int> mp;

 bool check(ll val)

 {

     for (int i = ; i < n; i++)

     {

         num[i] = ;

     }

     ll ans = , sum = ;

     int start = ;

     for (int i = ; i < n; i++)

     {

         sum += num[a[i]];

         num[a[i]]++;

         while (sum > val && start <= i)

         {

             sum -= --num[a[start]];

             start++;

         }

         ans += i - start + ;

     }

     return ans >= k;

 }

 int main()

 {

     scanf("%d", &t);

     while (t--)

     {

         scanf("%d %d", &n, &k);

         int cnt = ;

         for (int i = ; i < n; i++)

         {

             scanf("%d", &a[i]);

             if (mp.count(a[i]))

                 a[i] = mp[a[i]];

             else

             {

                 mp[a[i]] = cnt++;

                 a[i] = cnt - ;

             }

         }

         mp.clear();

         ll l = , r = (ll)n * (n - ) / , res = INF;

         while (l <= r)

         {

             ll m = (l + r) >> ;

             if (check(m))

             {

                 res = m;

                 r = m - ;

             }

             else

             {

                 l = m + ;

             }

         }

         printf("%lld\n", res);

     }

     return ;

 }

巴特西

hihocoder offer收割编程练习赛10 C 区间价值

最新文章

热门文章