2 条题解

  • 5
    @ 2023-11-18 23:03:03

    由题可知,本题让每次使用的两个纸条的长度加起来,直至纸条只剩一张。

    我们采取贪心策略,每次取中两个最小长度的纸条,使之粘成一个纸条,每一次都是最小的选择,那么最后的结果也必然是最小。

    若是采用sort进行排序,因为数据范围会超时。我们定义两个变量x,y为纸条的任意两个长度,遍历当前所有纸条,若其余长度大于x或y,则与之交换 ,使x, y成为最小值和次小值(也可以先sotr一遍,x, y为最小和次小)。之后保存两个数x,y之和,不断遍历寻找次小值或最小值,直至纸条数为一。

    若还有不理解,欢迎qq来问我

    这题还有一种比较简单的解法,就是使用优先队列,利用优先队列的特性,就能很轻松的写出来啦

    • 0
      @ 2023-12-14 16:30:18
      int main()
      {int n;
      cin >> n;
      /* 创建最小堆名为pq。*/
      priority_queue<int, vector<int>, greater<int> > pq;
      for (int i = 0; i < n; ++i)
      {
      int ai;
      cin >> ai;
      pq.push(ai);
      }
      long totalLength = 0;
      /*当仅剩一个纸条时结束。*/
      while (pq.size() > 1)
      {
      int min1 = pq.top();
      pq.pop();
      int min2 = pq.top();
      pq.pop();
      int newLength = min1 + min2;
      totalLength += newLength;
      /*将生成的新纸条压入。*/
      pq.push(newLength);
      }
      cout << totalLength << endl;
      return 0;
      }
      
      • 1

      BanG Dream!--我嘞个去(It's mygo!!!!!)

      信息

      ID
      939
      时间
      1000ms
      内存
      256MiB
      难度
      9
      标签
      递交数
      260
      已通过
      16
      上传者