网易8.8笔试

第1题.n个数最多能分成多少个质数之和

ac：100 思路：分成n个2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	ll sum=0,n,m;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&m);
		sum+=m/2; 
	}
	printf("%lld\n",sum);
}

第2题：序列最小 ac100

思路：模拟当前位置的数

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
int a[N],b[N],vis[N];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		 cin>>a[i];
		 vis[a[i]]=1;
	}
	a[m+1]=1e9;
	int i=1,k=1,c=0;
	while(i<=n){
		if(vis[i]==1) i++;
		else{
			if(i>a[k]) b[++c]=a[k],k++;
			else b[++c]=i,i++; 
		}
	}
	for(int i=1;i<n;i++) cout<<b[i]<<" ";
	cout<<b[n]<<endl;
	
}

第3题：将物品平均分给两个人，多余的丢弃，求最少丢弃的值？

ac:80 两重dfs爆栈了，应该dfs物品分给了哪个人。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=15;
int a[N],b[N],vis[N];
int n;
int maxx;
void dfs(int pos,int sum,int pre,int cnt){
	if(cnt==2&&sum>pre) return;
	if(sum==pre) maxx=max(maxx,sum);
	if(pos==n+1){
		if(cnt==2){
			return;
		}
		if(cnt==1){
			dfs(1,0,sum,2);
			return;
		}
	}
	if(vis[pos]==0){
		vis[pos]=1;
		dfs(pos+1,sum+a[pos],pre,cnt);
		vis[pos]=0;	
	}
	dfs(pos+1,sum,pre,cnt);
}
int main(){
	int T,m;
	cin>>T;
	while(T--){
		cin>>n;
		int sum=0;
		maxx=0;
		for(int i=1;i<=n;i++) vis[i]=0;
		for(int i=1;i<=n;i++){
			 cin>>a[i];
			 sum+=a[i];
		}
		sort(a+1,a+1+n);
		dfs(1,0,0,1);
		cout<<sum-2*maxx<<endl;
	}
}

第4题：求构成的生成树最大边和最小边的差值最小

ac:100 思路：枚举边求最小生成树复杂度m*n*o(并查集复杂度)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1005;
int p[N],n,m,minn=1e9;
struct node{
	int u,v,c;
}a[N*3];
bool cmp(node a,node b){
	if(a.c!=b.c) return a.c<b.c;
	return a.u<b.u; 
}
int find(int x){
	return x==p[x]?x:p[x]=find(p[x]);
}
bool fun(int s){
	
	if(n==1){
		minn=0;
		return true;
	}
	for(int i=1;i<=n;i++) p[i]=i;
	int cnt=0;
	for(int i=s;i<=m;i++){
		int x=find(a[i].u),y=find(a[i].v);
		if(x!=y){
			p[x]=y;
			cnt++;
		}
		if(cnt==n-1){
			minn=min(minn,a[i].c-a[s].c);
			return true;	
		}
	}
	return false;
}
int main(){
	
	cin>>n>>m;
	for(int i=1,u,v,c;i<=m;i++) cin>>a[i].u>>a[i].v>>a[i].c;
	sort(a+1,a+1+m,cmp);
	for(int i=1;i<=m;i++){
		bool c=fun(i);
		if(c==false) break;
	}
	cout<<minn<<endl;
}

#笔试题目##秋招##Java##求offer#