![洛谷 P7912：[CSP-J 2021 T4] 小熊的果篮 ← 双向链表](http://pic.xiahunao.cn/yaotu/洛谷 P7912：[CSP-J 2021 T4] 小熊的果篮 ← 双向链表)
【题目来源】https://www.luogu.com.cn/problem/P7912【题目描述】小熊的水果店里摆放着一排 n 个水果。每个水果只可能是苹果或桔子从左到右依次用正整数 1,2,…,n 编号。连续排在一起的同一种水果称为一个“块”。小熊要把这一排水果挑到若干个果篮里具体方法是每次都把每一个“块”中最左边的水果同时挑出组成一个果篮。重复这一操作直至水果用完。注意每次挑完一个果篮后“块”可能会发生变化。比如两个苹果“块”之间的唯一桔子被挑走后两个苹果“块”就变成了一个“块”。请帮小熊计算每个果篮里包含的水果。【输入格式】第一行包含一个正整数 n表示水果的数量。第二行包含 n 个空格分隔的整数其中第 i 个数表示编号为 i 的水果的种类1 代表苹果0 代表桔子。【输出格式】输出若干行。第 i 行表示第 i 次挑出的水果组成的果篮。从小到大排序输出该果篮中所有水果的编号每两个编号之间用一个空格分隔。【输入样例】121 1 0 0 1 1 1 0 1 1 0 0【输出样例】1 3 5 8 9 112 4 6 12710【数据范围】对于 10% 的数据n≤5。对于 30% 的数据n≤1000。对于 70% 的数据n≤50000。对于 100% 的数据1≤n≤2×10^5。【算法分析】● 由于数据规模较大建议 C/C 选手使用 scanf 和 printf 语句输入、输出。● 高效地删除元素并合并相邻块双向链表是最合适的数据结构。● it fruits.erase(it) 整体作用等价于1. 删除 it 指向的元素2. 让 it 指向被删元素的下一个元素。---每次都把每一个“块”中最左边的水果同时挑出即从块中删除元素。● 若用 STL list 模拟会有 3 个样例超时TLE。问题出在 STL list 的 erase 操作上。虽然 list 的 erase 是 O(1)但每一轮都需要遍历整个链表而且每次删除都会导致大量迭代器移动。如下是 70 分代码3 个 TLE。#include bits/stdc.h using namespace std; /* Use a list to store fruits, with each element being a pair of type,number */ listpairint,int fruits; int main() { int n; scanf(%d,n); for(int i1; in; i) { int type; scanf(%d,type); fruits.push_back({type,i}); } vectorvectorint ans; while(!fruits.empty()) { vectorint block; int last_type-1; /* Traverse the linked list and extract the leftmost element of each block */ auto itfruits.begin(); while(it!fruits.end()) { if(it-first!last_type) { block.push_back(it-second); last_typeit-first; itfruits.erase(it); } else { last_typeit-first; it; } } sort(block.begin(),block.end()); ans.push_back(block); } for(auto block:ans) { for(int i0; iblock.size(); i) { printf(%d ,block[i]); } printf(\n); } return 0; } /* in: 12 1 1 0 0 1 1 1 0 1 1 0 0 out: 1 3 5 8 9 11 2 4 6 12 7 10 */【算法代码】#include bits/stdc.h using namespace std; const int N2e55; int ans[N],le[N],ri[N],a[N]; int n,len,z,y; int main() { cinn; a[0]a[n1]-1; for(int i1; in; i) { scanf(%d,a[i]); le[i]i-1,ri[i]i1; if(a[i]!a[i-1]) { ans[len]i; } } while(len) { int t0; for(int i1; ilen; i) { printf(%d ,ans[i]); zle[ans[i]],yri[ans[i]]; le[y]z,ri[z]y; if(a[ans[i]]a[y] a[z]!a[y]) ans[t]y; } lent; coutendl; } return 0; } /* in: 12 1 1 0 0 1 1 1 0 1 1 0 0 out: 1 3 5 8 9 11 2 4 6 12 7 10 */【参考文献】https://blog.csdn.net/acker007/article/details/135043572https://www.luogu.com.cn/problem/solution/P7912https://blog.csdn.net/joseph0530/article/details/132946346
【题目来源】https://www.luogu.com.cn/problem/P7912【题目描述】小熊的水果店里摆放着一排 n 个水果。每个水果只可能是苹果或桔子从左到右依次用正整数 1,2,…,n 编号。连续排在一起的同一种水果称为一个“块”。小熊要把这一排水果挑到若干个果篮里具体方法是每次都把每一个“块”中最左边的水果同时挑出组成一个果篮。重复这一操作直至水果用完。注意每次挑完一个果篮后“块”可能会发生变化。比如两个苹果“块”之间的唯一桔子被挑走后两个苹果“块”就变成了一个“块”。请帮小熊计算每个果篮里包含的水果。【输入格式】第一行包含一个正整数 n表示水果的数量。第二行包含 n 个空格分隔的整数其中第 i 个数表示编号为 i 的水果的种类1 代表苹果0 代表桔子。【输出格式】输出若干行。第 i 行表示第 i 次挑出的水果组成的果篮。从小到大排序输出该果篮中所有水果的编号每两个编号之间用一个空格分隔。【输入样例】121 1 0 0 1 1 1 0 1 1 0 0【输出样例】1 3 5 8 9 112 4 6 12710【数据范围】对于 10% 的数据n≤5。对于 30% 的数据n≤1000。对于 70% 的数据n≤50000。对于 100% 的数据1≤n≤2×10^5。【算法分析】● 由于数据规模较大建议 C/C 选手使用 scanf 和 printf 语句输入、输出。● 高效地删除元素并合并相邻块双向链表是最合适的数据结构。● it fruits.erase(it) 整体作用等价于1. 删除 it 指向的元素2. 让 it 指向被删元素的下一个元素。---每次都把每一个“块”中最左边的水果同时挑出即从块中删除元素。● 若用 STL list 模拟会有 3 个样例超时TLE。问题出在 STL list 的 erase 操作上。虽然 list 的 erase 是 O(1)但每一轮都需要遍历整个链表而且每次删除都会导致大量迭代器移动。如下是 70 分代码3 个 TLE。#include bits/stdc.h using namespace std; /* Use a list to store fruits, with each element being a pair of type,number */ listpairint,int fruits; int main() { int n; scanf(%d,n); for(int i1; in; i) { int type; scanf(%d,type); fruits.push_back({type,i}); } vectorvectorint ans; while(!fruits.empty()) { vectorint block; int last_type-1; /* Traverse the linked list and extract the leftmost element of each block */ auto itfruits.begin(); while(it!fruits.end()) { if(it-first!last_type) { block.push_back(it-second); last_typeit-first; itfruits.erase(it); } else { last_typeit-first; it; } } sort(block.begin(),block.end()); ans.push_back(block); } for(auto block:ans) { for(int i0; iblock.size(); i) { printf(%d ,block[i]); } printf(\n); } return 0; } /* in: 12 1 1 0 0 1 1 1 0 1 1 0 0 out: 1 3 5 8 9 11 2 4 6 12 7 10 */【算法代码】#include bits/stdc.h using namespace std; const int N2e55; int ans[N],le[N],ri[N],a[N]; int n,len,z,y; int main() { cinn; a[0]a[n1]-1; for(int i1; in; i) { scanf(%d,a[i]); le[i]i-1,ri[i]i1; if(a[i]!a[i-1]) { ans[len]i; } } while(len) { int t0; for(int i1; ilen; i) { printf(%d ,ans[i]); zle[ans[i]],yri[ans[i]]; le[y]z,ri[z]y; if(a[ans[i]]a[y] a[z]!a[y]) ans[t]y; } lent; coutendl; } return 0; } /* in: 12 1 1 0 0 1 1 1 0 1 1 0 0 out: 1 3 5 8 9 11 2 4 6 12 7 10 */【参考文献】https://blog.csdn.net/acker007/article/details/135043572https://www.luogu.com.cn/problem/solution/P7912https://blog.csdn.net/joseph0530/article/details/132946346
