80 分,求这份代码的复杂度
查看原帖
80 分,求这份代码的复杂度
726139
残阳如血楼主2025/1/1 15:45
/*

初始想法:

再用链表连接每一个块

跳着删除并且合并

每一个快表示:
  1. 是 0 还是 1
  2. 长度
  3. 第一个元素的下标

---

考虑漏了情况

合并后块内下标是不连续的!

解决方法:
  不用合并,每次如果取完那么就删除当前块
  如果访问到一个块,其 val 与前一个相同,则直接跳过,不输出(实际上已经合并了)

---

发现此时若同一块为 begin 及下一个,则两个会同时输出

可以延时删除,输出完后在删除
*/

#include <bits/stdc++.h>
const int N = 2e5 + 10;

struct Data {
  int val; // 这个块是 0 还是 1
  int len; // 块长,实时维护
  int pos; // 第一个元素的下标,实时维护

  Data(int _val, int _len, int _pos) : val(_val), len(_len), pos(_pos) {}
};

int n;

std::list<Data> a;

void init() { // 读入并初始化块
  scanf("%d", &n);
  for (int i = 1, t; i <= n; ++i) {
    scanf("%d", &t);
    if (a.empty() || t != a.back().val) { // 新的块
      a.push_back(Data(t, 1, i)); // 值为输入的 t,长度为 1,从下标 i 开始
    } else { // 加入上一个块
      ++a.back().len; // 长度 +1
    }
  }
}

int main() {
  init();

  // std::cerr << a.size() << "\n";

  while (!a.empty()) { // 还有水果
    for (auto it = a.begin(); it != a.end(); ++it) { // 遍历每一个块
      if (it != a.begin()) {
        auto pre = it; --pre;
        if (pre->val == it->val) { // 前后 val 相同,同一块
          continue;
        }
      }

      printf("%d ", it->pos); // 输出每个块第一个水果的编号
      ++it->pos, --it->len; // 第一个水果下标变大,长度变小
    }
    puts("");

    for (auto it = a.begin(); it != a.end(); ) {
      if (it->len != 0) ++it;
      else it = a.erase(it);
    }
  }

  return 0;
}
2025/1/1 15:45
加载中...