【题解】AC狗修AC-学徒篇

视频题解点击此处查看

题目阅读

​ AC狗在厂里面打工，要维修空调。 每个空调由许多配件组成，AC狗主要负责压缩机，冷凝器，蒸发器三件主要配件。如果其中有个出了问题空调都没办法工作。

​ 现在厂里来了一批返修空调，空调的三个配件有可能有以下三种状态：

​ 1、正常:不需要修理

​ 2、损坏:需要换零件

​ 3、待修理：可以修好，但是需要成本，损坏程度决定修理成本，但是也可以直接换新的。

​ 现在厂里三种配件还有若干，如果要把空调都修好，问你修好这批空调

题意抽象

​ 有三个序列，同时每个序列中有几次操作将序列中的几个数值化为0(操作次数为 替换的配件数 - 损坏配件)，问你三种序列的和最小值为多少。

算法分析

​ 本题利用贪心思想，首先计算出每种配件能够剩余替换的数量，在输入的过程中如果碰到配件损坏的情况，则将替换用的配件数量-1，将损坏配件变为正常配件(即成本为0的状态)，之后根据耗费修理成本大小进行降序排序，如果有当前序列当中有多余的操作机会将配件替换，让成本变为0，则从头往后替换至机会耗尽。最后将替换完毕的序列进行累加则为最小值

代码讲解

#include <iostream>
#include <algorithm>

using namespace std;

int a[1100000], b[1100000], c[1100000];

int main()
{
 int n, t1 = 0, t2 = 0, t3 = 0;
 int l1, l2, l3;
 long long fee = 0;
 cin >> n;
 for (int i = 1; i <= n; i++)
 {
  cin >> a[i] >> b[i] >> c[i];
  if (a[i] == -1)
   t1++;
  if (b[i] == -1)
   t2++;
  if (c[i] == -1)
   t3++;
 }
 cin >> l1 >> l2 >> l3;
 l1 -= t1;
 l2 -= t2;
 l3 -= t3;
 sort(a + 1, a + n + 1);
 sort(b + 1, b + n + 1);
 sort(c + 1, c + n + 1);
 for (int i = n; i >= 1; i--)
 {
  if (a[i] != -1)
  {
   if (l1 > 0)
    l1--;
   else
    fee += a[i];
  }
  if (b[i] != -1)
  {
   if (l2 > 0)
    l2--;
   else
    fee += b[i];
  }
  if (c[i] != -1)
  {
   if (l3 > 0)
    l3--;
   else
    fee += c[i];
  }
 }
 cout << fee << endl;
 return 0;
}