北京制作网站公司哪家好,邯郸招聘网,百度招聘平台,报名网站制作给定n个数A1...An#xff0c;小Ho想了解AL..AR中有多少对元素值相同。小Ho把这个数目定义为区间[L,R]的价值#xff0c;用v[L,R]表示。 例如1 1 1 2 2这五个数所组成的区间的价值为4。 现在小Ho想知道在所有的的v[L,R](1 L R n)中#xff0c;第k小的值是多少… 给定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小的值是多少。 Input 第一行一个数T(T10)表示数据组数。 对于每一组数据 第一行两个数nk1n200,000,1kn*(n1)/2 第二行n个数A1…An(1Ai1,000,000,000) Output 一个数表示答案。 Sample Input 2
4 7
1 1 2 3
3 6
100 100 100 Sample Output 0
3题意我们给出n个数我们求任意一段区间他们相同的数的次数就是区间的值然后我们按值排序求第k个区间的值是多少思路开始我用的n2果断超时。。然后我们看到ai的范围有这么大我们又要记录次数显然我们可以用map但是我用map也超时了所以有个高级的操作因为n的范围数组能开的下只是ai值大而已所以我们可以离散化然后我们想一下怎么求答案呢如果我们直接求出所有的区间再排序输出的话n2复杂度所以发现不行我们仔细想想我们能得知我们区间长度越小我们的区间值肯定更小我们可以二分去处理二分的话最小值是0没有一个相同最大的时候也就是全部的数都相同可以推出是n*(n-1)/2因为我们要求是求第k个区间的值那么我们就只要去寻找判断小于当前数的区间个数有多少个如果小于这个数的区间比k还大的话说明我们当前的数肯定比我们要求的小所以我们向右扩展反之亦然然后我们想如何去求多少个区间比他小呢我们可以不用求出所有区间的值为什么呢因为我们区间的个数和值的大小息息相关如果[l.r]是比k小的那么[l,r-1],[l,r-2]....[l,l]都是小于k的数这里就用到了我们的尺取法那么我们就把它变成了一个nlogn的算法 #includecstdio
#includecmath
#includecstring
#includemap
#includealgorithm
using namespace std;
typedef long long ll;
ll a[200001];
ll t,n,m,temp[200001];
ll vis[200001];
ll check(ll mid)//尺取求比mid小的区间个数
{int i,j;ll sum0;ll num0;memset(vis,0,sizeof(vis));for(i0,j0;in;i){for(;jnsumvis[a[j]]mid;j){sumvis[a[j]];vis[a[j]];}numj-i;//尺取思想核心vis[a[i]]--;sum-vis[a[i]];}return numm;
}
int main()
{ll ans;scanf(%lld,t);while(t--){scanf(%lld%lld,n,m);for(int i0;in;i){scanf(%lld,a[i]);temp[i]a[i];}int cnt;sort(temp,tempn);//离散化cnt unique(temp,tempn) - temp;for(int i 0 ; i n ; i)a[i] lower_bound(temp,tempcnt,a[i]) - temp;ll left0,right((ll)n*((ll)n-1))/2;while(leftright){ll mid(leftright)/2;if(check(mid))//如果小于mid的区间个数比m多的话说明值还不够小{ansmid;rightmid-1;}else{leftmid1;}}printf(%lld\n,ans);}
} 转载于:https://www.cnblogs.com/Lis-/p/9393788.html
