深信服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);
}

 

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

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

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 深信服8月25日笔试的两道编程题
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏