原题：某餐馆有n张桌子，每张桌子有一个参数：a 可容纳的最大人数； 有m批客人，每批客人有两个参数:b人数，c预计消费金额。 在不允许拼桌的情况下，请实现一个算法选择其中一部分客人，使得总预计消费金额最大

卷前：水平太菜，花了好几个小时写到现在，结果到最后时间复杂度超过一秒提交不了（JAVA写的）

卷中：放代码，测试数据在卷尾

 

class Table implements Comparable<Table> {
  public int max;
  public boolean visited;

  public Table(int max) {
    this.max = max;
  }

  @Override
  public int compareTo(Table o) {
    if (o.max > this.max)
      return 1;// 降序
    return -1;
  }

  @Override
  public String toString() {
    return "Table [max=" + max + ", visited=" + visited + "]";
  }

}

class Guest implements Comparable<Guest> {
  public int num;
  public int cost;
  public boolean isSet = false;

  public Guest(int num, int cost) {
    this.num = num;
    this.cost = cost;
  }

  @Override
  public int compareTo(Guest o) {
    if (o.num > this.num) {
      return 1;
    } else if (o.num == this.num) {
      if (o.cost > this.cost) {
        return 1;
      } else {
        return -1;
      }
    } else {
      return -1;
    }
  }

  @Override
  public String toString() {
    return "Guest [num=" + num + ", cost=" + cost + "]";
  }

}

public class Main {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    // 输入n张桌子，m批客人
    int n = scan.nextInt();
    int m = scan.nextInt();
    // 输入n个参数a表示每张桌子可容纳的最大人数
    Table[] tables = new Table[n];
    Guest[] guests = new Guest[m];
    for (int i = 0; i < n; i++) {
      int a = scan.nextInt();
      // System.out.println("第"+(i+1)+"张桌子 最大人数是："+a);
      tables[i] = new Table(a);
    }
    // 输入m组参数 人数b 预计消费c
    for (int i = 0; i < m; i++) {
      int b = scan.nextInt();
      int c = scan.nextInt();
      // System.out.println("第"+(i+1)+"组 人数："+b+"消费："+c);
      guests[i] = new Guest(b, c);
    }
    //
    Arrays.sort(guests);
    Arrays.sort(tables);
    // for(Guest g:guests) {
    // System.out.println(g);
    // }
    // for(Table t:tables) {
    // System.out.println(t);
    // }
    // 遍历桌子，放入人数
    int out = 0;
    boolean isFirst = true;
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        //
        if (guests[i].num <= tables[j].max && !tables[j].visited && !guests[i].isSet) {
          // 还要看是不是后面有更多钱的
          int max = guests[i].cost;
          for (int temp = i; temp < m; temp++) {
            if (guests[temp].num <= tables[j].max && !tables[j].visited && !guests[temp].isSet
                && (j + 1 != n) ? (guests[temp].num > tables[j + 1].max) : true) {
              if (max < guests[temp].cost) {
                guests[temp].isSet = true;
                max = guests[temp].cost;
              }
            }
          }
          guests[i].isSet = true;
          tables[j].visited = true;
          out += max;
          if (isFirst)// 第一批最肥客人如果没找到合适num桌子就跳下一批否则会直接跳下一桌
            isFirst = false;
          break;
        }
        if (isFirst)
          break;
      }
    }
    // 输出
    System.out.println(out);
  }

}

 

 

卷后：还得多练习

思路：

1. 桌子降序，客源按人数降序、人数相同则按预计花费降序；
2. 从第一个最大（a最大）的桌子开始放客。（细节，如果第一次放不到合适的，即isFirst，直接break到下一批客源，否则会break到下一个桌子，导致空桌子）；
3. 放成功则isVisited，isSet标记；
4. 后面的桌子放的时候需要判断是否后面会有更肥（cost更高的）的客源，有就放后面的（细节，后面的客源需要判断下人数guests[temp].num是否小于当前桌子加一（tables[j+1]）的桌子大小tables[j+1].max）；
5. 挨个从高到低杀猪完成（中途后面有肥的就贪婪先杀了…）。
6. 全剧终，完了时间复杂度超过1s，提交失败。

测试数据：

3 5

2 4 2

1 3

3 5

3 7

5 9

1 10

答案：20

解析输入：

3 5 #分别为桌子3张，客源5批

2 4 2 #分别为桌子① 2个位置 桌子②4个位置 桌子③2个位置

1 3 #客源①1个人 3单元花费 √

3 5 #客源②3个人 5单元花费 ×

3 7 #客源③3个人 7单元花费 √

5 9 #客源④5个人 9单元花费 ×

1 10 #客源⑤1个人 10单元花费 √