题目3 : 区间价值

时间限制: 10000ms
单点时限: 1000ms
内存限制: 256MB

描述

给定n个数A1...An,小Ho想了解AL..AR中有多少对元素值相同。小Ho把这个数目定义为区间[L,R]的价值,用v[L,R]表示。

例如1 1 1 2 2这五个数所组成的区间的价值为4。

现在小Ho想知道在所有的的v[L,R](1 <= L <= R <= n)中,第k小的值是多少。

输入

第一行一个数T(T<=10),表示数据组数。

对于每一组数据:

第一行两个数n,k(1<=n<=200,000,1<=k<=n*(n+1)/2)

第二行n个数A1…An(1<=Ai<=1,000,000,000)

输出

一个数表示答案。

样例输入

2
4 7
1 1 2 3
3 6
100 100 100

样例输出

0
3
又是一题二分题,比赛时没做出来。。。。看别人代码懂了。。

思路:问第k小的结果,就二分答案。用双指针(好像专业点的方法叫尺取法)验证答案。

几个点要考虑:

1.k会爆int,答案也会爆int

2.尺取法的算法思路

3.二分别写错了。。。- -反正我经常写错

 
  1. #include <bits/stdc++.h>
  2. const int N = 200010;
  3. using namespace std;
  4. typedef long long ll;
  5. int num[N];
  6. int a[N], n;
  7. ll k;
  8. map< int, int>mp;
  9. bool judge(ll x)
  10. {
  11. ll cur = 0, rk = 0;
  12. int l = 0;
  13. for ( int i = 0; i < n; i++)
  14. a[i] = 0; //统计当前有多少个数
  15. for ( int i = 0; i < n; i++)
  16. {
  17. cur += a[num[i]]; //把当前数贡献的价值加进去
  18. a[num[i]]++;
  19. while (cur > x) //要求小于等于k的区间价值个数,值大于x要减去
  20. {
  21. cur -= --a[num[l++]]; //把最开始的数价值贡献减去
  22. }
  23. rk += i - l + 1; //如果[l, i]区间的价值小于等于x,那么i不动,l增加,
  24. //得到的价值只会更小,所以以l开头,i结尾的区间都符合要求
  25. }
  26. return rk >= k; //小于等于当前值的区间数大于等于k,就把答案扩进二分的区间了。
  27. }
  28. int main()
  29. {
  30. int T;
  31. scanf( "%d", &T);
  32. while (T--)
  33. {
  34. int tot = 0;
  35. mp.clear();
  36. scanf( "%d%lld", &n, &k);
  37. for ( int i = 0; i < n; i++)
  38. {
  39. scanf( "%d", num + i);
  40. if (mp.find(num[i]) == mp.end())
  41. mp[num[i]] = tot++; //离散化方便后面统计
  42. num[i] = mp[num[i]];
  43. }
  44. ll l = 0, r = (ll)n*(n -1)/ 2;
  45. while (l < r)
  46. {
  47. ll mid = (l + r)>> 1;
  48. if (judge(mid))
  49. r = mid; //答案在区间里面,则更小范围的区间是[l, mid]
  50. else
  51. l = mid + 1; //答案不在区间在答案在[mid+1, r]区间
  52. }
  53. printf( "%lld\n", l);
  54. }
  55. return 0;
  56. }