信息学奥赛一本通 2077：【21CSPJ普及组】小熊的果篮(fruit)

本文主要是介绍信息学奥赛一本通 2077：【21CSPJ普及组】小熊的果篮(fruit) | 洛谷 P7912 [CSP-J 2021] 小熊的果篮，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目链接】

信息学奥赛一本通 2077：【21CSPJ普及组】小熊的果篮(fruit)
洛谷 P7912 [CSP-J 2021] 小熊的果篮

【题目考点】

1. 链表

2. stl list

3. stl set

【解题思路】

解法1：链表中包含链表

创建一个block双向链表，block链表中的每个元素都是一个“块”。
（之所以建双向链表，是因为下面有在block链表中删除结点的操作，双向链表删除写起来相对比较容易。如果使用单链表也可以完成该题。）
每个“块”也是一个单向链表，叫做fruit链表，保存这一个块中每个水果的编号。
首先根据读入的序列，创建block链表。

如果当前读入数字（水果编号）和上个数字相同，则把当前数字加到当前fruit链表之中。
否则在block链表中用尾插法添加一个元素（fruit链表），新的fruit链表添加水果编号

每次遍历block链表，在block链表中的每个“块”中（fruit链表）取第一个数字输出，并删除fruit链表中的第一个数字。
如果当前fruit链表在删除数字后，成为空链表，那么需要在block链表中删除该空链表，并判断前一个链表和后一个链表的水果种类是否相同，如果相同，则合并两个单链表（即把后一个链表接到前一个链表的后面）。

针对该解法可以自己写链表，也可以使用STL list类来完成。

解法2：使用两个set

set的原理是红黑树，可以维护一个有序序列，可以使用lower_bound或upper_bound成员函数以 $O (l o g n)$ 复杂度找到其中符合某一条件的元素。
设两个set：st0与st1。st0：保存种类为0的水果的编号 st1：保存种类为1的水果的编号
每次循环，从st0与st1哪个集合的最小值更小，就从哪个集合开始。交替在st0与st1中选择数字，下一次在另一个集合中选择出的数字要比上一次选择出的数字更大，并删除数字。直到在另一个集合中选择出的数字没有比上一次选择出的数字更大，则跳出循环。

由于set使用lower_bound的复杂度是 $O (l o g n)$ ，该过程需要做n次，总体复杂度为 $O (n l o g n)$ ，是可以接受的。

【题解代码】

解法1：链表中包含链表

写法1：自己写链表

#include <bits/stdc++.h>
using namespace std;
#define N 200005
struct Fruit//fruit链表中结点类型 
{int num;//num：水果编号 int next;//单链表下一个结点的地址 
};
Fruit fruit[2*N];//由于有头结点，总结点数多于N 
int fp, ft;
int TEST;
struct Block//block链表中结点类型 
{int type, head, tail;//type:水果种类  head：头指针 tail：尾指针 int pre, next;//pre, next：双向链表中前一个结点及下一个结点的地址int front(){return fruit[fruit[head].next].num;}void push_back(int num){fruit[++fp].num = num;fruit[tail].next = fp;tail = fp;}void pop_front(){head = fruit[head].next;}bool empty(){return head == tail;}void merge(Block bk)//当前链表末尾连接新链表 新链表为bk {fruit[tail].next = fruit[bk.head].next;tail = bk.tail;} 
};
Block block[N];
int bp, bhead = ++bp, btail = bhead;
void block_push_back(int type, int fruitNum)//type：水果类型 fruitNum：第一个水果编号 
{block[++bp].type = type;block[bp].head = block[bp].tail = ++fp;//在添加结点时，才给该block内的fruit链表设头结点 block[bp].push_back(fruitNum);block[bp].pre = btail;block[btail].next = bp;btail = bp;
}
bool block_empty()
{return bhead == btail;
}
void block_erase(int ep)//删掉地址为ep的结点 
{block[block[ep].pre].next = block[ep].next;block[block[ep].next].pre = block[ep].pre;if(btail == ep)btail = block[ep].pre;
}
int main()
{int n, a, lastNum = -1;//ln:上一次读入的数 cin >> n;for(int i = 1; i <= n; ++i){cin >> a; if(a == lastNum)block[btail].push_back(i);else{block_push_back(a, i);lastNum = a;}}while(block_empty() == false)//block链表不空 {for(int i = block[bhead].next; i != 0; i = block[i].next){//取出每块第一个水果，并删除水果的Fruit结点 cout << block[i].front() << ' ';block[i].pop_front();}cout << endl;for(int i = block[bhead].next; i != 0; i = block[i].next)//删除没有水果的块 if(block[i].empty())block_erase(i);int i = block[bhead].next;while(block[i].next != 0)//合并块i,nx{ int nx = block[i].next;if(block[i].type == block[nx].type){block[i].merge(block[nx]);block_erase(nx);}elsei = block[i].next;}}return 0;
}

写法2：使用stl list

#include <bits/stdc++.h>
using namespace std;
#define N 200005
typedef list<list<int> >::iterator BlockIt;
typedef list<int>::iterator It;
list<list<int> > block;
int f[N];//f[i]：第i个水果是什么 
int main()
{int n, a, lastNum = -1;//ln:上一次读入的数 cin >> n;for(int i = 1; i <= n; ++i){cin >> a;f[i] = a;if(a == lastNum)prev(block.end())->push_back(i);//block最后元素添加i else{list<int> fruit;fruit.push_back(i);block.push_back(fruit);lastNum = a;}}while(block.empty() == false){BlockIt bi; for(bi = block.begin(); bi != block.end(); ++bi){//输出头 cout << bi->front() << ' ';bi->pop_front();}cout << endl;bi = block.begin();while(bi != block.end()){//删除 if(bi->empty())bi = block.erase(bi);//删掉bi指向的结点，并让bi指向下一个结点 else++bi;}bi = block.begin(); while(next(bi) != block.end()){BlockIt pi = bi++;//pi在前，bi在后，判断pi，bi指向的结点是否可以合并 if(f[*pi->begin()] == f[*bi->begin()]){//类型相同， 可以合并 pi->splice(pi->end(), *bi);block.erase(bi);bi = pi;}}}return 0;
}

解法2：使用两个set

#include <bits/stdc++.h>
using namespace std;
#define N 200005
set<int> st[2];//st[0]：保存种类为0的水果的编号 st[1]：保存种类为1的水果的编号 
int main()
{int n, a, p, lastNum; cin >> n;for(int i = 1; i <= n; ++i){cin >> a;if(a == 0)st[0].insert(i);elsest[1].insert(i);}while(!(st[0].empty() && st[1].empty())){if(st[0].empty())//确定p中起始下标位置 p = 1;else if(st[1].empty())p = 0;else if(*st[0].begin() > *st[1].begin())p = 1;elsep = 0;lastNum = -1;while(true){set<int>::iterator it = st[p].lower_bound(lastNum); if(it == st[p].end())break;cout << *it << ' ';lastNum = *it;st[p].erase(it);p = (p+1)%2;//p从0变为1，1变为0； }cout << endl; }return 0;
}