10.21考试

题不是很难,但是考炸了
T1因为不熟悉一个知识点导致用了麻烦的方法
虽然时间复杂度和空间复杂度都ok
但是常数大,只有加快读才能过;
而且我输出还写错了
T1
一个小模拟,因为细节和没写快读炸了
有一个小知识点不熟:最大值个数,不用排序
T2
可以把所有人分成4个部分,正男,负男,正女,负女;
然后再烤虑贪心就好了,再用一个双指针;

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e5+7;
int n,ans;
int a[N],b[N],c[N],d[N];
int cmp(int x,int y){
	return x>y;
}
int main(){
	freopen("ples.in","r",stdin);
	freopen("ples.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		int y=abs(x);
		if(x<0){
			a[0]++;
			a[a[0]]=y;
		}
		if(x>0){
			b[0]++;
			b[b[0]]=y;
		}
	}
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		int y=abs(x);
		if(x<0){
			c[0]++;
			c[c[0]]=y;
		}
		if(x>0){
			d[0]++;
			d[d[0]]=y;
		}
	}
	sort(a+1,a+a[0]+1,cmp);
	sort(b+1,b+b[0]+1,cmp);
	sort(c+1,c+c[0]+1,cmp);
	sort(d+1,d+d[0]+1,cmp);
	int l=1;
	for(int i=1;i<=a[0];i++){
		while(l<=d[0]&&a[i]<=d[l])l++;
		if(l<=d[0]) ans++;
		l++;
	}
	l=1;
	for(int i=1;i<=c[0];i++){
		while(l<=b[0]&&c[i]<=b[l])l++;
		if(l<=b[0]) ans++;
		l++;
	}
	cout<<ans;
	fclose(stdin);
	fclose(stdout);
	return 0;
}
/*
1
-1800
1800

1
1700
-1800

2
-1800
-2200
1900 
1700
*/

T3
最后一题,注意体面是选法,当时考试的时候卡住了,因为分成两半搜索卡住了,
后来才明白可以选负数,这样就相当于在第一组加值,所以就可以折半了;
因为要求的是选法,所以用set维护一下就好了,

上一篇:汇编指令之set


下一篇:python 自定义sorted排序