2020年牛客算法入门课练习赛1
A 第K小数
题目描述：
给你一个长度为n的序列，求序列中第k小数的多少。
思路：
因为数字比较小，用桶排序，可以做到O(n)
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=5e6+10;
inline int read(){
int x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if (ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (x<<1) + (x<<3) + (ch^48);
ch = getchar();
}
return x * f;
}
int t;
int a[N];
int gs[N];
int main()
{
scanf("%d",&t);
while(t--) {
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) gs[i]=0;
for(int i=1;i<=n;i++) {
a[i]=read();
gs[a[i]]++;
}
int pos=1,ans=1;
while(k) {
if(gs[pos]<k) {
k-=gs[pos];
pos++;
}else {
ans=pos;
k=0;
}
}
printf("%d\n",ans);
}
} B 不平行的直线
题目描述：
个点，两两形成一条直线，问最多有多少条不平行且不重合的直线
思路：
使用 去重即可，对于一条直线直接保存斜率的分子分母
，化成最简并且
同号即可，时间复杂度
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=500;
int gcd(int a,int b) {
return b==0?a:gcd(b,a%b);
}
int x[N],y[N];
set<pair<int,int> >s;
void cl(int a,int b) {
int X=x[a]-x[b];
int Y=y[a]-y[b];
int g=gcd(X,Y);
X/=g;
Y/=g;
if(X<0) X*=-1,Y*=-1;
s.insert(make_pair(X,Y));
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d%d",&x[i],&y[i]);
}
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
cl(i,j);
}
}
printf("%d\n",int(s.size()));
} C 丢手绢
题目描述：
个人，围成一圈，已知相邻人的距离，求最远的两个人的距离
思路：
预处理顺时针距离前缀和，可以 求出两个人之间的最短距离，逆时针用总长减去顺时针即可。然后使用尺取法的思想，对于第
个人找到离他最远的
，那么对于
来说离他最远的一定大于
，那么就可以
的时间解决了。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int d[N];
int sum[N];
int n;
int R;
int dis(int x,int y) {
return sum[y-1]-sum[x-1];
}
int js(int x,int y) {
return min(dis(x,y),R-dis(x,y));
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&d[i]);
R+=d[i];
}
for(int i=1;i<=n+1;i++) {
sum[i]=sum[i-1]+d[i];
}
int j=2;
int ans=0;
for(int i=1;i<=n;i++) {
while(j<n&&js(i,j)<=js(i,j+1)) {
j++;
}
//cout<<i<<" "<<j<<endl;
ans=max(ans,js(i,j));
}
printf("%d\n",ans);
} D 二分
题目描述：
裁判有一个数字 ，
次询问，每一次猜一个数字，返回3种结果，
分别代表猜对了，猜的大了，猜的小了 。问最多有多少个返回结果同时合法。
思路：
可以枚举数字 的值，我们将每次猜的数字和加一、减一都保存下到
数组，可以发现，其中必然存在一个数字可以作为
并且是结果最大。所以枚举数组里的值即可。
假设每次查询数字 ，那么合法的结果个数就是下面三种情况个数的和。
返回 . 的等于 的个数
返回 + 的大于 的个数
返回 - 的小于 的个数
取最大值即可。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>v1,v2,v3;
vector<int>v;
int n;
int js(int x) {
int p1,p2;
int ans=0;
p1=lower_bound(v1.begin(),v1.end(),x)-v1.begin();
p2=upper_bound(v1.begin(),v1.end(),x)-v1.begin();
ans+=p2-p1;
p1=upper_bound(v2.begin(),v2.end(),x)-v2.begin();
p2=v2.size();
ans+=p2-p1;
p1=lower_bound(v3.begin(),v3.end(),x)-v3.begin();
ans+=p1;
return ans;
}
int main() {
scanf("%d",&n);
char c;
int x;
for(int i=1;i<=n;i++) {
scanf("%d %c",&x,&c);
if(c=='.') v1.push_back(x);
if(c=='+') v2.push_back(x);
if(c=='-') v3.push_back(x);
v.push_back(x+1);
v.push_back(x);
v.push_back(x-1);
}
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end());
sort(v3.begin(),v3.end());
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
int ans=0;
for(int a:v) {
ans=max(ans,js(a));
}
printf("%d\n",ans);
} E 交换
题目描述：
n个数字，要求从小到大排列，问最少交换两个数字几次。
思路：
可以发现，对于一个 这种的类型的交换，需要的是点个数-1次交换，那么对于这个序列来说，我们只要计算出所有这种类型的交换集，然后答案就是总点数-交换集的个数。
对于该问题，可以转化成图论来解决，即求环的个数。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
int a[N],b[N];
bool vis[N];
vector<int>v;
int getid(int x) {
return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
vector<int>e[N];
void dfs(int u) {
vis[u]=1;
for(int a:e[u]) {
if(!vis[a]) {
dfs(a);
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
v.push_back(a[i]);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
for(int i=1;i<=n;i++) {
b[i]=getid(a[i]);
}
for(int i=1;i<=n;i++) {
e[i].push_back(b[i]);
}
int ans=0;
for(int i=1;i<=n;i++) {
if(!vis[i]) {
ans++;
dfs(i);
}
}
printf("%d\n",n-ans);
} 
