CF472B 题解

Blikewsr · 2022-08-19 16:57:46 · 题解

• 题目大意
  有 n 个人， 每个人都有自己想要到达的楼层， 第 i 想要去第 f_i 层。 同时有一个电梯， 电梯的最大承受人数为 k。 求电梯的最小运行层数。

• 思路
  要求电梯的最小运行层数， 我们就要先知道单次电梯的运行层数怎么求。

  假设电梯里有 m 个人 (m \le k)m, 其中第 i 个人的希望到达层数为 f_i, 那么该次电梯的运行数为所有人的希望到达层数的最大值， 即 \max \{ f_1, f_2......f_{m-1}, f_m \}

  其次， 因为单次电梯的运行层数为电梯里所有人的希望到达层数的最大值。 所以， 我们可以尽可能地把希望到达层数较大的人放在一起， 同时乘坐电梯， 同时尽可能地将电梯装满。

  接着， 由于电梯从 1 楼上去后还要回到 1 楼。 所以， 在计算电梯单次运行层数时要乘 2. 同时， 电梯从第 1 楼到 t 层共走了 t - 1 层。 所以， 单次电梯的运行层数为 2 * (f[i] - 1).

  最后， 因为要尽可能地将希望到达层数较大的人放在一起， 所以我们可以先把所有人的希望到达层数从大到小排序一下就可以了。

• 代码

  #include <bits/stdc++.h>
  #define int long long
  #define N 1000000
  using namespace std;
  inline int read() {   // 快读 
    int f = 0, n = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') n *= -1;
        ch = getchar();   
    }
    while (isdigit(ch)) {
        f = (f << 1) + (f << 3) + ch - '0';
        ch = getchar();
    }
    return f * n; 
  }
  int cmp(int x, int y) {   // sort排序用的  
    return x > y;  // 从大到小排序 
  }
  int n, k, tot, f[N];
  /*
  n   : 人数
  k   : 电梯的最大承受人数
  tot : 最终结果， 即电梯的最小运行层数
  f[] : 用来储存所有人希望到达的楼层 
  */
  signed main() {  // 主函数 
    n = read(), k = read();
    for (int i = 1; i <= n; ++ i) f[i] = read();
    // 输入， 具体见上注释 
    sort (f + 1, f + n + 1, cmp);
    // 排序， 使所有人希望到达的楼层数按从大到小的顺序 
    for (int i = 1; i <= n; i += k) {
        // 每次装满电梯， 所以 i += k 
        tot += 2 * (f[i] - 1);    
        /*
            因为电梯上去后还要回到第 1 层, 所以要乘 2 
            从第 1 层到第 i 层共走了 (i - 1) 层
            单次电梯运行数为电梯里最大的希望到达数 
        */
    }
    printf ("%d\n", tot);
    // 输出最终结果 
    return 0;   // 完美结束 
  } 

• 此题解仅供参考， 谢谢！