题目: 区间价值

描述

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

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

现在小Ho想知道在所有的的vL,R中，第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

思路

暴力枚举求出n*(n+1)/2区间不同的值，然后排序求第k小的值，明显TLE。
我们先分析发现区间越大，价值肯定越大，并且呈单调性。我们就可以用二分去查找第k小的值。
对于每次二分的check，这里利用尺取的思想，尺取从左往右扫一遍最大区间[L,R]里的价值都是小于二分的mid,O(n)时间内在n个数里求出比mid价值小的区间个数。
总的时间复杂度就变成O(nlogn)。

消费排行榜：少女》小孩、老人、狗》男人

11
好基友可以基到什么程度?

“该发生的都发生了不该发生的都尽力了”

“真正的兄弟是在对方需要女人的时候.
做他的女人”

ob1 = ‘abc’
ob2 = iter(‘abc’)
ob3 = iter(‘abc’)

for i in ob1:
print(i, end=’,’)
》a,b,c,

ob1.next() # AttributeError: ‘str’ object has no attribute ‘next‘

for i in ob2:
print(i, end=’ ‘) # a b c
ob2.next() # StopIteration:

ob3.next() # a
ob3.next() # b
ob3.next() # c
ob3.next() # StopIteration:

通过_上述例子可看出，迭代器的优势在于支持自遍历，同时，它的特点是单向非循环的，一旦完成遍历，再次调用就会报错。

男上加男
迎男而上
强人锁男
左右为男
在劫男逃
男终羞涩
一女男求

世界上有两种人有话不直说，一种是中国人，一种是女人。我们面对的是中国女人。

“昨天他给我讲他小时候的故事，讲到一半突然不讲了，他说：“你嫁给我吧让我妈妈给你讲”。

离散化

离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：
原数据：1,999,100000,15；处理后：1,3,4,2；
原数据：{100,200}，{20,50000}，{1,400}；
处理后：{3,4}，{2,6}，{1,5}；

二分

不解释

尺取法

顾名思义，像尺子一样取一段，借用挑战书上面的话说，尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的时候，所以说尺取法是一种高效的枚举区间的方法，是一种技巧，一般用于求取有一定限制的区间个数或最短的区间等等。当然任何技巧都存在其不足的地方，有些情况下尺取法不可行，无法得出正确答案，所以要先判断是否可以使用尺取法再进行计算。

使用尺取法时应清楚以下四点：

  • 1、什么情况下能使用尺取法?
  • 2、何时推进区间的端点？
  • 3、如何推进区间的端点？
  • 4、何时结束区间的枚举？

尺取法通常适用于选取区间有一定规律，或者说所选取的区间有一定的变化趋势的情况，通俗地说，在对所选取区间进行判断之后，我们可以明确如何进一步有方向地推进区间端点以求解满足条件的区间，如果已经判断了目前所选取的区间，但却无法确定所要求解的区间如何进一步得到根据其端点得到，那么尺取法便是不可行的。首先，明确题目所需要求解的量之后，区间左右端点一般从最整个数组的起点开始，之后判断区间是否符合条件在根据实际情况变化区间的端点求解答案。

例题

1、 Poj3061
题意：给定一个序列，使得其和大于或等于S，求最短的子序列长度。
输入：n=10, S=15, array={5,1,3,5,10,7,4,9,2,8}

个人理解：设置两个指针，首先右指针不断的+1向右，直到满足条件。如果到结尾了就没有答案。否则就停止右指针进行左指针+1，首先判断当前是否满足条件，满足就继续左指针，不满足就右指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <cstdio>  
#include <algorithm>  
#include <cstring>  
#define MAX 100005  
#define LL long long  
#define INF 0x3f3f3f3f  
  
using namespace std;  
LL a[100010];  
int n, t, ans = INF;  
LL sum, s;  
  
int main()  
{  
    scanf("%d", &t);  
    while (t--){  
        scanf("%d %I64d", &n, &s);  
        for (int i = 0; i < n; i++) scanf("%I64d", a+i);  
        int st = 0, en = 0;  
        ans = INF; sum = 0;  
        while (1){  
            while (en<n && sum<s) sum += a[en++];  
            if (sum < s) break;  
            ans = min(ans, en-st);  
            sum -= a[st++];  
        }  
        if (ans == INF) ans = 0;  
        printf("%d\n", ans);  
    }  
    return 0;  
}

#