P7912 [CSP-J 2021] 小熊的果篮

· · 题解

题目描述

小熊的水果店里摆放着一排 n 个水果。每个水果只可能是苹果或桔子，从左到右依次用正整数 1、2、3、……、n 编号。连续排在一起的同一种水果称为一个“块”。小熊要把这一排水果挑到若干个果篮里，具体方法是：每次都把每一个“块”中最左边的水果同时挑出，组成一个果篮。重复这一操作，直至水果用完。注意，每次挑完一个果篮后，“块”可能会发生变化。比如两个苹果“块”之间的唯一桔子被挑走后，两个苹果“块”就变成了一个“块”。请帮小熊计算每个果篮里包含的水果。

题解

首先对输入序列建双向链表，维护每一个“假块”头建双向链表，共维护两个链表。

这里的“假块”指每个“假块”中水果种类必定相同，但相邻“假块”中水果种类可能相同。

我们可以使用双向链表的删除元素来模拟吃一个水果。

不断循环遍历“假块”头链表，遍历过程中记录上一个被吃水果种类。遍历到某个块头时，若其指向的水果与上一个被吃水果种类相同，直接将这个块头删除，相当于合并块；若不同，吃掉这个水果，更新上一个被吃水果种类，将这个块头指向的水果变成被吃水果的下一个水果。

关于一个假块被吃完的处理方法，此时这个假块的块头一定会指向下一个块头。若这个块头的种类与被吃水果的种类不同，删掉这个块，因为遍历下一个块时将会吃掉这个水果；若相同，不动，因为接下来的过程将会把下一个块的块头删除。这样保证遍历时不会出现长度小于一的假块。若假块没有被吃完，其指向的下一个水果一定与吃掉的种类相同，同样不做任何处理。

每个水果被遍历一次，每个块被删除一次，时间复杂度 \Theta(n)。

代码如下：

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int MAXN = 2e5+10;

struct Node{
  int prev;
  int val;
  int next;
};

int n;

int shuiguo[MAXN];
Node headList[MAXN];
Node shuiguoList[MAXN];
int cc;

void EatOne(int pos) {
  int prev = shuiguoList[pos].prev;
  int next = shuiguoList[pos].next;
  shuiguoList[prev].next = next;
  shuiguoList[next].prev = prev;
  printf("%d ", pos);
}

void Del(int pos) {
  int prev = headList[pos].prev;
  int next = headList[pos].next;
  headList[prev].next = next;
  headList[next].prev = prev;
}

void Chi() {
  int solo = headList[0].next;
  int nowcolor = shuiguo[headList[solo].val];
  while (solo!=cc+1) {
    if (shuiguo[headList[solo].val]!=nowcolor) {
      Del(solo);
      solo = headList[solo].next;
      continue;
    }
    EatOne(headList[solo].val);
    headList[solo].val = shuiguoList[headList[solo].val].next;
    if (shuiguo[headList[solo].val]!=nowcolor) {
      Del(solo);
    }
    solo = headList[solo].next;
    nowcolor^=1;
  }
  putchar('\n');
}

int main() {
  scanf("%d", &n);
  shuiguoList[0].next = 1;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &shuiguo[i]);
    shuiguoList[i].prev = i-1;
    shuiguoList[i].next = i+1;
  }
  shuiguo[0] = 2;
  shuiguo[n+1] = 2;
  headList[0].next = 1;
  for (int i = 1; i <= n; i++) {
    if (shuiguo[i]!=shuiguo[i-1]) {
      cc++;
      headList[cc].prev = cc-1;
      headList[cc].next = cc+1;
      headList[cc].val = i;
    }
  }
  while (shuiguoList[0].next!=n+1) {
    Chi();
  }
  return 0;
}