Fork me on GitHub

[51Nod]P1686 第K大区间

传送门

注意到如果我们设$f_i$表示值大于$i$的区间有多少个的话,那么显然$i$越大,区间的个数越小,具有单调性,所以显然可以二分解决.
又因为题目中的限制可以转化为$f_i>=k$并且$i$最大.那么我们可以去二分这个$i$然后统计一下$f_i$有多少个.
那么现在的问题就是怎么去统计这个$f_i$到底有多少.
我们先对原数组进行离散化处理(因为原来的权值范围实在是太大了),然后开一个$buck_i$表示$i$这个数字出现了多少次.
那么发现如果我们使用$two$_$pointers$统计答案的话,那么每次会更新众数的那个值一定只能是新加进来的那个值.
所以我们只需要判断一下是不是$buck_r>=mid$即可.

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5 + 10;

int n , k;
struct Node {
int id;
int v;
}ls[N];
int num[N] , idx;
int buck[N];

inline bool cmp ( Node x , Node y ) {
return x.v < y.v;
}

int pos[N];
vector < int > G[N];
inline int check ( int x ) {
if ( x == 1 )
return n * ( n - 1 ) / 2;
int ans = 0 , L = 0;
for ( int i = 1 ; i <= n ; i++ )
G[i].clear();
memset ( buck , 0 , sizeof ( buck ) );
for ( int i = 1 ; i <= n ; i++ ) {
if ( buck[num[i]] >= x - 1 )
pos[i] = G[num[i]][buck[num[i]] + 1 - x];
else
pos[i] = 0;
L = max ( L , pos[i] );
ans += L;
buck[num[i]]++;
int tmp = buck[num[i]];
G[num[i]].push_back( i );
}
return ans;
}

signed main ( void ) {
ios :: sync_with_stdio ( false );
cin.tie ( 0 ) , cout.tie ( 0 );
cin >> n >> k;
for ( int i = 1 ; i <= n ; i++ ) {
ls[i].id = i;
cin >> ls[i].v;
}
sort ( ls + 1 , ls + 1 + n , cmp );

ls[0].v = -1;
for ( int i = 1 ; i <= n ; i++ ) {
if ( ls[i].v != ls[i - 1].v )
idx++;
num[ls[i].id] = idx;
}
int l = 1 , r = n , ans = 1;
while ( l <= r ) {
int mid = ( l + r ) >> 1;
if ( check ( mid ) >= k ) {
l = mid + 1;
ans = mid;
}
else
r = mid - 1;
}
cout << ans << endl;
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:[51Nod]P1686 第K大区间

文章作者:KRrrrrrrrr

发布时间:2019年10月24日 - 09:10

最后更新:2019年10月24日 - 10:10

原始链接:http://krrrr.xyz/2019/10/24/51NodP1686-第K大区间/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。