邓老师的题目质量还不错，好些日子没刷题了，拿来复习算法练练手并记下一些总结
A-第K小数
给你一个长度为n（10*5e6）的序列，求序列中第k小数的多少。
一个很经典的题了，做法很多：
1.序列全部排序后取第k个，时间复杂度O(nlogn)
2.维护一个大小为k的大根堆，先填满堆，然后后面的a[i]与堆顶元素比较更新堆，时间复杂度O(nlogk)
3.利用快排基准分割+二分的思想，不断调整答案区间，时间复杂度O(n)
这里数据量较大，只有方法3能过，当然c++里的nth_element()函数也是基于方法3实现的，但加了一些优化，比手写的快了3倍左右
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e6+5;
typedef long long ll;
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 partition(int a[],int l,int h){
int pivot = a[l];
while (l<h) {
while(l<h && a[h]>=pivot) h--;
a[l]=a[h];
while(l<h && a[l]<=pivot) l++;
a[h]=a[l];
}
a[l]=pivot;
return l;
}
int a[maxn];
int main(){
int T=read();
while(T--){
int n=read(),k=read();
for(int i=0;i<n;i++) a[i]=read();
int l=0,r=n-1;
while(l<r){
int mid = partition(a,l,r);
if(mid>=k) r=mid;
else l=mid+1;
}
printf("%d\n",a[l-1]);
}
return 0;
} B-不平行的直线
在坐标纸上有N（200）个不重合的点，两两可以连一个线段并延伸成直线，请问在这些直线里最多能选出多少条使得他们两两不平行也不重合。
只要求不平行和不重合，那只要枚举所有直线将斜率相同的直线去重后统计有多少不同的斜率
直接用double小数记录斜率可能有误差，用pair记录分数形式，注意要化为最简形式和分子分母符号的统一
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3+5;
typedef long long ll;
set<pair<int,int>>st;
int x[maxn],y[maxn];
int main(){
int n; scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d%d",&x[i],&y[i]);
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
int fz=y[j]-y[i],fm=x[j]-x[i];
int d = __gcd(fz,fm);
fz/=d,fm/=d;
if(fz<0) fz*=-1,fm*=-1;
st.insert(make_pair(fz,fm));
}
}
printf("%d\n",st.size());
return 0;
} C-丢手绢
一个圆上有N（1e5）个点，给出相邻两个点的距离，求任意两个点最小距离的最大值。
因为是圆，可以想到枚举点x的时候，最远的点y是可以通过三分得到的，check的话将圆展开一条线统计前缀和就可以计算x到y的最小距离
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
typedef long long ll;
int n;
int a[maxn],sum[maxn];
int calc(int x,int y){
int x1 = sum[x]+sum[n+1]-sum[y];
int x2 = sum[y]-sum[x];
return min(x1,x2);
}
int main(){
scanf("%d",&n);
sum[1]=0;
for(int i=2;i<=n+1;i++){
scanf("%d",&a[i]);
sum[i]=sum[i-1]+a[i];
}
int ans=0;
for(int i=1;i<=n;i++){
int l=1,r=n;
while(l<r){
int lmid=l+(r-l)/3;
int rmid=r-(r-l)/3;
if(calc(i,lmid)<calc(i,rmid)) l=lmid+1;
else r=rmid-1;
}
ans = max(ans,calc(i,l));
}
printf("%d\n",ans);
return 0;
} D-二分
二分猜数字，给出一些猜数字的结猜测果，符号如果是“+”说明猜的数比答案大，“-”说明比答案小，“.”说明猜到了答案。问最多能有多少次是符合猜测结果的。
1e5条记录，每条记录中猜的数都小于int类型最大值，考虑离散化，假如离散化后的区间为[1,m]，猜的数是x，对于“+”，那么在[1,x-1]区间上+1，对于“-”，那么在[x+1,m]区间上+1，对于“.”，那么在[x,x]区间上+1，最后找到[1,m]上的最大值就是符合最多猜测结果的次数。
1.离散化后线段树单点更新+区间更新
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,o<<1
#define rson mid+1,r,o<<1|1
const int maxn = 3e5+5;
typedef long long ll;
int sum[maxn<<2],lazy[maxn<<2];
void pushdown(int o){
if(lazy[o]){
int v = lazy[o];
lazy[o<<1] += v;
lazy[o<<1|1] += v;
sum[o<<1] += v;
sum[o<<1|1] += v;
lazy[o] = 0;
}
}
void update(int L,int R,int v,int l,int r,int o){
if(L>R) return;
if(L<=l&&r<=R){
sum[o]+=v;
lazy[o]+=v;
return;
}
pushdown(o);
int mid=(l+r)>>1;
if(L<=mid) update(L,R,v,lson);
if(R>mid) update(L,R,v,rson);
}
int mx=0;
void down(int l,int r,int o){
if(l==r){
mx=max(mx,sum[o]);
return;
}
pushdown(o);
int mid=(l+r)>>1;
down(lson);
down(rson);
}
int a[maxn],b[maxn];
vector<int>vc;
int main(){
int n;
scanf("%d",&n);
char op[2];
for(int i=0;i<n;i++){
scanf("%d %s",&a[i],op);
vc.push_back(a[i]); //这里因为所有x不一定是连续的，所以将前后两个数也加进来
vc.push_back(a[i]-1);
vc.push_back(a[i]+1);
if(op[0]=='.') b[i]=0;
else if(op[0]=='-') b[i]=-1;
else if(op[0]=='+') b[i]=1;
}
sort(vc.begin(),vc.end());
vc.erase(unique(vc.begin(),vc.end()),vc.end());
int m = vc.size();
for(int i=0;i<n;i++){
a[i]=lower_bound(vc.begin(),vc.end(),a[i])-vc.begin()+1;
if(b[i]==0) update(a[i],a[i],1,1,m,1);
else if(b[i]==-1) update(a[i]+1,m,1,1,m,1);
else if(b[i]==1) update(1,a[i]-1,1,1,m,1);
}
down(1,m,1);
printf("%d\n",mx);
return 0;
} 2.还有一种巧妙的做法，利用map直接记录差分值，然后求前缀和的最大值
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
typedef long long ll;
map<int,int>mp;
ll inf = 1LL<<40;
int main(){
int n;
scanf("%d",&n);
char op[2];
int x;
for(int i=0;i<n;i++){
scanf("%d %s",&x,op);
if(op[0]=='.'){
mp[x]++;
mp[x+1]--;
}
else if(op[0]=='+'){
mp[-inf]++;
mp[x]--;
}
else if(op[0]=='-'){
mp[x+1]++;
}
}
int mx=0,sum=0;
for(auto it:mp){
sum += it.second;
mx = max(mx,sum);
}
printf("%d\n",mx);
return 0;
} E-交换
求交换一个序列中任意两个元素的最少次数使得序列从小到大排序。序列长度1e5，所有元素不相同。
将原序列排好序的作为对比，如果a[i]不在排好序的对应位置上的话，直接交换到对应位置上去，然后更新记录位置的信息，这样交换次数是最少的。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
typedef long long ll;
int a[maxn],b[maxn];
map<int,int>pos;
int main(){
int n; scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
pos[a[i]]=i;
}
sort(b,b+n);
int ans=0;
for(int i=0;i<n;i++){
if(a[i]==b[i]) continue;
int p=pos[b[i]];
pos[a[p]]=i;
pos[a[i]]=p;
swap(a[i],a[p]);
ans++;
}
printf("%d\n",ans);
} 注意：如果是限制交换相邻的元素，那就是和插入排序一样了，最少需要交换原序列的逆序数次。
京公网安备 11010502036488号