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))。

实现：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <map>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 typedef long long ll;
 9 
10 const ll INF = 0x3f3f3f3f3f3f3f3f;
11 
12 int t, n, k, a[200005], num[200005];
13 map<int, int> mp;
14 
15 bool check(ll val)
16 {
17     for (int i = 0; i < n; i++)
18     {
19         num[i] = 0;
20     }
21     ll ans = 0, sum = 0;
22     int start = 0;
23     for (int i = 0; i < n; i++)
24     {
25         sum += num[a[i]];
26         num[a[i]]++;
27         while (sum > val && start <= i)
28         {
29             sum -= --num[a[start]];
30             start++;
31         }
32         ans += i - start + 1;
33     }
34     return ans >= k;
35 }
36 
37 int main()
38 {
39     scanf("%d", &t);
40     while (t--)
41     {
42         scanf("%d %d", &n, &k);
43         int cnt = 0;
44         for (int i = 0; i < n; i++)
45         {
46             scanf("%d", &a[i]);
47             if (mp.count(a[i]))
48                 a[i] = mp[a[i]];
49             else
50             {
51                 mp[a[i]] = cnt++;
52                 a[i] = cnt - 1;
53             }
54         }
55         mp.clear();
56         ll l = 0, r = (ll)n * (n - 1) / 2, res = INF;
57         while (l <= r)
58         {
59             ll m = (l + r) >> 1;
60             if (check(m))
61             {
62                 res = m;
63                 r = m - 1;
64             }
65             else
66             {
67                 l = m + 1;
68             }
69         }
70         printf("%lld
", res);
71     }
72     return 0;
73 }