深信服8月25日笔试的两道编程题

  时间:2020-08-27 10:52:15  阅读量:995  评论数:0  作者:马小超i

深信服8月25日笔试的两道编程题主要介绍的是

第一题比较难,我是在算小样例中总结出的规律,第二题比较简单。好在都AC了

第一题:

题目描述:

给你N棵树,每棵树都有一个高度a[i],  (N和a[i]都是一百万数量级)
你每次可以施展魔法让其中一棵树不生长而其它树高度都加一,
问最少几次魔法可以使得所有树一样高。

分析:

对于次高的树来说,想要达到最高的高度,我们只需要施展【他们高度差值】的次数魔法。

例如两棵树的高度是6和4,那么只需要2次让6不动,4就可以变成6.

当然这只是对于最高的树只有一棵来说的,若是有m棵最高的树,则次高树想变成最高树需要施展【m*高度差值】次数的魔法。 

例如三棵树6 6 4,想变成相等高度的树,需要2*2=4次,具体过程是【6 7 5】 【7 7 6】 【7 8 7】【8 8 8】

当然这里次高树的棵树是没有影响的。

例如次高树也有两颗,但是答案不变,假如4棵树6 6 4 4,具体过程【6 7 5 5】【7 7 6 6】【8 7 7 7】【8 8 8 8】

有了把次高树变成最高树的策略,那所有问题都解决了,因为次高树变成了最高树,那么再考虑次次高树,次次次高树即可,所有的都可以由这一个策略算出来。

这里需要注意的是,魔法只会针对最高树使用,因为遏制其他的树生长只会让差值越来越大,与我们的目的相反。

解法:

先把N棵树按高度排序,并且去重,统计每个高度树的棵树。

在解决最高树和次高树的过程中,我们要维护以下几个关键的有用的量:

一、次高树与最高树的高度差: int cha=maxx-(b[i] ans);

随着越来越多的树变成了最高树的高度,次高树的高度也在随着变化,他们变成了【本身高度 魔法次数】的高度。

二、使用魔法的次数    ans =cha*m;

如上述分析,次高树想变成最高树需要施展【m*高度差值】次数的魔法。 

三、最高树的高度   maxx =cha*(m-1);

最高树的高度变化与普通树不同,对于除了最高树之外的普通树来说,魔法施展几次,他们就会增加几,因为他们从不被遏制生长。

但是最高树会被魔法遏制,所以在次高树变成最高树的时候,最高树的高度只是增加了【差值次数*(最高树棵树-1)】的高度。

这里可以参照分析的例子【6 6 4 4】,经过4次变化,达到了【8 8 8 8】的高度,两棵高度为4的树生长高度对应魔法次数4,但是最高树因为被遏制只生长了2,也就是【差值次数*(最高树棵树-1)】的高度。

四、最高树的棵树   m =c[i];    

次高树变成了最高树之后,要统计入答案。

维护了这4个量,我们就可以O(n)时间求出答案。最重要的是理解最高树和普通的树在高度变化过程中的数量差异。

代码:

#include<iostream>
#include<cstdio> 
#include<algorithm>
using namespace std;

int a[1000050];
int b[1000050];
int c[1000050];
int n;

bool cmp(int x,int y){
	return x>y;
}

int main(){
	cin>>n;
	for (int i=1; i<=n; i  ){
		scanf("%d",&a[i]);
	} 
	//排序去重 
	sort(a 1,a n 1,cmp);
	b[1]=a[1];
	c[1]=1;
	int p=1;
	for (int i=2; i<=n; i  ){
		if (a[i]!=b[p]){
			p  ;
			b[p]=a[i];
			c[p]=1;
		} else c[p]  ;
	}

	int maxx=b[1]; //最大值 
	int m=c[1];  //最大值个数 
	long long ans=0;
	for (int i=2; i<=p; i  ){
		int cha=maxx-(b[i] ans);
		ans =cha*m;
		maxx =cha*(m-1);
		m =c[i];	
	}
	cout<<ans<<endl; 
} 

第二题:

题目:

给你一个长度一百万的字符串s,全是由0-9的数字构成,
再给你一百万次的修改操作,每次操作两个数x,y,表示把字符串s中所有的x都换成y。
最后输出字符串s。

分析:

一百万次的修改操作,其中无用的或者重复的很多,因为10*10最多才100种组合,其中不乏很多把2变成4,再把2变成6的操作,或者把2变成4,把4变成6的操作,所以不要在没有最终情况下去动字符串,而是先处理好这个规则。

解法:

开一个大小为10数组a,下标表示字符串中的原数,内容a[i]则表示最终将变成的值。

对于一个修改操作x,y来说,需要在数组找所有的a[i]==x,若有需要执行a[i]=x.

代码就是: for (int i=0; i<=9; i ) if (a[i]==x) a[i]=y; 

假设修改操作是2->4  4->6,

    在a数组中原来是i和a[i],一一对应的,修改2->4时,找到的a[2]=x,然后执行a[2]=4.

    当修改4->6时,for循环中a[2]和a[4]都等于x,所以得修改a[2]=6 a[4]=6.

重点是:一个数只能变成另一个数字,但是一个数字的来源是不唯一的,所以我们要将x变成y的话需要遍历一遍数组去检查所有的a[i]有哪些原始的i变成了x,这些x都需要修改。

最后变换字符串即可。

代码:

#include<iostream>
#include<cstring>
#include<cstdio> 
using namespace std;

char s[1000050];
int a[100];
int n,x,y;

int main(){
	for (int i=0; i<=9; i  ){
		a[i]=i;
	} 
	scanf("%s",s);
	int len=strlen(s);
	cin>>n;
	for (int o=1; o<=n; o  ){
		scanf("%d%d",&x,&y);
		for (int i=0; i<=9; i  ){
			if (a[i]==x) a[i]=y; 
		}
	} 
		
	for (int j=0; j<len; j  ){
		s[j]=a[(s[j]-48)] 48;
	}
	
	printf("%s",s);
}

 

关键词:深信服,信服,8月25日,25日,笔试,编程