首页 > 深信服8月25日笔试的两道编程题 都AC了。
头像
马小超i
编辑于 2020-08-25 21:59
+ 关注

深信服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)时间求出答案。最重要的是理解最高树和普通的树在高度变化过程中的数量差异。

代码:

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. using namespace std;
  5. int a[1000050];
  6. int b[1000050];
  7. int c[1000050];
  8. int n;
  9. bool cmp(int x,int y){
  10. return x>y;
  11. }
  12. int main(){
  13. cin>>n;
  14. for (int i=1; i<=n; i++){
  15. scanf("%d",&a[i]);
  16. }
  17. //排序去重
  18. sort(a+1,a+n+1,cmp);
  19. b[1]=a[1];
  20. c[1]=1;
  21. int p=1;
  22. for (int i=2; i<=n; i++){
  23. if (a[i]!=b[p]){
  24. p++;
  25. b[p]=a[i];
  26. c[p]=1;
  27. } else c[p]++;
  28. }
  29. int maxx=b[1]; //最大值
  30. int m=c[1]; //最大值个数
  31. long long ans=0;
  32. for (int i=2; i<=p; i++){
  33. int cha=maxx-(b[i]+ans);
  34. ans+=cha*m;
  35. maxx+=cha*(m-1);
  36. m+=c[i];
  37. }
  38. cout<<ans<<endl;
  39. }

详见博客:

全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐