2019.10.02考试报告

T1

一般都能想到二分+取前m大正值,但是复杂度无法承受,我们发现要的是sum值,并不需要每个位置的准确值,

所以用可以nth_element把大于第m大的放右边即可。(原来nth还可以这么用)。

nth_element实现:

每次找一个base,小于base的放右边,大于的放右边

2019.10.02考试报告
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e8+10;
 4 int n,k,a[N];
 5 inline int read()
 6 {
 7         register int sum,k=1;register char s;
 8         while(s=getchar(),s<'0'||s>'9') if(s=='-') k=-1; sum=s-'0';
 9         while(s=getchar(),s>='0'&&s<='9') sum=sum*10+s-'0';
10         return k*sum;
11 }
12 void NTH(int k,int l,int r)
13 {
14         vector<int>v[3];
15         int x=a[l],tot=l-1;
16         for(int i=l;i<=r;i++) 
17         {
18                 if(a[i]<x) v[0].push_back(a[i]);
19                 else if(a[i]==x) v[2].push_back(a[i]);
20                 else v[1].push_back(a[i]);
21         }
22         for(int i=0;i<v[0].size();i++) a[++tot]=v[0][i];
23         for(int i=0;i<v[2].size();i++) a[++tot]=v[2][i];
24         for(int i=0;i<v[1].size();i++) a[++tot]=v[1][i];
25         if(k<=v[0].size()) NTH(k,l,l+v[0].size()-1);
26         else if(k>v[0].size()&&k<=v[0].size()+v[2].size()) return;
27         else NTH(k-v[0].size()-v[2].size(),l+v[0].size()+v[2].size(),r);
28 }
29 int main()
30 {
31         //freopen("1.in","r",stdin);
32         //freopen("1.out","w",stdout);
33         n=read(),k=read();
34         for(int i=1;i<=n;i++) a[i]=read();
35         NTH(k,1,n);
36         printf("%d",a[k]);
37         return 0;
38 }
NTH

时间复杂度最坏O(n^2),但一般是O(n)的,空间O(n)(好像可以O(1)但咕了),跑1e7的点跑800ms。

然而T1卡手打nth_element,我和kx赛后都被卡了。

 

T2,T3

暂时咕了

 

2019.10.02考试报告

 

上一篇:CSS高级选择器以及使用案例——电影排行榜


下一篇:LeetCode——Nth Highest Salary