信奥赛-刷题笔记-队列篇-T4-P7912小熊的果篮

总题单

​

本部分总题单如下

【腾讯文档】副本-CSP-JS+NOI 题单 (未完待续)

https://docs.qq.com/sheet/DSmJuVXR4RUNVWWhW?tab=BB08J2

队列篇题单

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

题目描述

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

输入格式

第一行，包含一个正整数 $n$，表示水果的数量。

第二行，包含 $n$ 个空格分隔的整数，其中第 $i$ 个数表示编号为 $i$ 的水果的种类，$1$ 代表苹果，$0$ 代表桔子。

输出格式

输出若干行。

第 $i$ 行表示第 $i$ 次挑出的水果组成的果篮。从小到大排序输出该果篮中所有水果的编号，每两个编号之间用一个空格分隔。

输入输出样例 #1

输入 #1

12
1 1 0 0 1 1 1 0 1 1 0 0

输出 #1

1 3 5 8 9 11
2 4 6 12
7
10

输入输出样例 #2

输入 #2

20
1 1 1 1 0 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0

输出 #2

1 5 8 11 13 14 15 17
2 6 9 12 16 18
3 7 10 19
4 20

输入输出样例 #3

输入 #3

见附件中的 fruit/fruit3.in。

输出 #3

见附件中的 fruit/fruit3.ans。

说明/提示

【样例解释 #1】

这是第一组数据的样例说明。

所有水果一开始的情况是 $[1,1,0,0,1,1,1,0,1,1,0,0]$，一共有 $6$ 个块。

在第一次挑水果组成果篮的过程中，编号为 $1,3,5,8,9,11$ 的水果被挑了出来。

之后剩下的水果是 $[1,0,1,1,1,0]$，一共 $4$ 个块。

在第二次挑水果组成果篮的过程中，编号为 $2,4,6,12$ 的水果被挑了出来。

之后剩下的水果是 $[1,1]$，只有 $1$ 个块。

在第三次挑水果组成果篮的过程中，编号为 $7$ 的水果被挑了出来。

最后剩下的水果是 $[1]$，只有 $1$ 个块。

在第四次挑水果组成果篮的过程中，编号为 $10$ 的水果被挑了出来。

【数据范围】

对于 $10\%$ 的数据，$n\le 5$。
对于 $30\%$ 的数据，$n\le 1000$。
对于 $70\%$ 的数据，$n\le 50000$。
对于 $100\%$ 的数据，$1\le n\le 2\times {10}^5$。

【提示】

由于数据规模较大，建议 C/C++ 选手使用 scanf 和 printf 语句输入、输出。

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
//#include<windows.h>using namespace std;
int n,cnt,t[200010];//n个水果 当前剩余的水果总数  t数组存水果 // 定义结构体 表示一个水果块
struct kuai{int st;//开始位置int ed;//结束位置int th;//类型 0为桔子，1为水果 
} f,x,ad; queue<kuai> q,q2;//q是主队列 q2是临时队列用于合并
bool used[200010];//标记某个位置是否已被取出 int main(){// 输入水果数量和具体的水果类别 scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&t[i]);}// 在末尾添加一个与最后一个不同的值，方便统一处理分段// 哨兵 t[n+1] = !t[n];// 分段处理：相同连续值的水果合并成"块"  ,si表示块的起始位置 // i=2是因为 不需要比较t[0] for(int i=2,si=1;i<=n+1;i++){// 如果和下一个值不一样 说明是不同块 if(t[i]!=t[i-1]){// 创建一个新块 [si,i-1],类型为t[i-1] //q.push((kuai){si,i,t[i-1]}) ; //ed应该为i-1q.push((kuai){si,i-1,t[i-1]}) ;si=i;//更新块的起始位置为下一个块的位置 }} cnt = n;//当前剩余的水果总数 // 打印队列中的所有块（不会破坏原队列）
//    queue<kuai> tmp_q = q; // 复制队列
//    while (!tmp_q.empty()) {
//        kuai block = tmp_q.front();
//        printf("%d %d %d\n", block.st, block.ed, block.th);
//        tmp_q.pop();
//    }/*1 3 13 5 05 8 18 9 09 11 1*/// 开始循环 直到所有水果都被取出 while(cnt){int has_output = 0; // 新增标志位：本轮是否输出了水果// 对当前所有块进行一次操作：取出每个块的第一个未被取出的水果while(q.size()){// f为每个块 f=q.front();q.pop();// used[f.st]==1 跳过已经被取出的元素// f.st <= f.ed 表示当前块中起始坐标小于等于结束坐标// 找到第一个可用的位置 f.st++ 更新st坐标  while (used[f.st]==1 && f.st <= f.ed) f.st++;// 如果这个块已经没有可用的了if(f.st>f.ed) continue;// 输出当前取出的水果位置，并标记为已使用printf("%d ", f.st);has_output = 1;cnt--;used[f.st] = true;// 如果该块只剩这一个水果，不再加入下一轮处理if (f.ed == f.st) continue;// 否则更新该块的起始位置，压入临时队列 q2f.st++;q2.push(f);} // 所有块处理完一轮后换行if(has_output) putchar('\n');//else break; // 不能终端 会影响接下来的合并// 合并临时队列中的块，并放回主队列 q 中while (q2.size()) {ad = q2.front(); q2.pop();// 尝试与后面的块合并（如果类型相同）while (q2.size()) {x = q2.front();if (x.th == ad.th) {ad.ed = x.ed; // 合并块，延长结束位置q2.pop();     // 删除已合并的块} else {break;}}// 合并完成的块重新放入主队列 qq.push(ad);}
//        Sleep(1);}return 0;
}
/*
12
1 1 0 0 1 1 1 0 1 1 0 0*/

现场真题注意事项

https://cspoj.com/contest.php?cid=1002Fus5yz4x3EcSJH1Z

注意事项

文件名（程序名和输入输出文件名）必须使用英文小写。（提交必须使用freopen()进行提交）

C/C++ 中函数 main() 的返回值类型必须是 int，程序正常结束时的返回值必须是0。

提交的程序代码文件的放置位置请参考各省的具体要求。

因违反以上三点而出现的错误或问题，申述时一律不予受理。

若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。

程序可使用的栈空间内存限制与题目的内存限制一致。

全国统一评测时采用的机器配置为：Inter® Core™ i7-8700K CPU @3.70GHz，内存 32GB。上述时限以此配置为准。

只提供 Linux 格式附加样例文件。

评测在当前最新公布的 NOI Linux 下进行，各语言的编译器版本以此为准

假设输入样例数据存在文件test.in中，输出样例数据存在文件test.out中，

则在CSP、NOI等比赛的代码中，需添加freopen、fclose语句，

内容详见模板代码如下。

#include <bits/stdc++.h>
#include<cstdio>//必须包含cstdio头文件
#include<iostream>
using namespace std;int main(){freopen("test.in","r",stdin);freopen("test.out","w",stdout);cout<<"Hello NOI"<<endl;fclose(stdin);fclose(stdout);return 0;
}

复制

下面为函数的简介，详细可参见 http://www.cplusplus.com/reference/clibrary/cstdio/freopen.html

函数名：freopen

声明：FILE freopen( const char path, const char mode, FILE stream );

所在文件： stdio.h

参数说明：

path: 文件名，用于存储输入输出的自定义文件名。

mode: 文件打开的模式。和fopen中的模式（如r-只读, w-写）相同。

stream: 一个文件，通常使用标准流文件。

返回值：成功，则返回一个path所指定文件的指针；失败，返回NULL。（一般可以不使用它的返回值）

功能：实现重定向，把预定义的标准流文件定向到由path指定的文件中。标准流文件具体是指stdin、stdout和stderr。其中stdin是标准输入流，默认为键盘；stdout是标准输出流，默认为屏幕；stderr是标准错误流，一般把屏幕设为默认。通过调用freopen，就可以修改标准流文件的默认值，实现重定向。

#include<iostream>
#include<cstdio>
using namespace std;
int main(){freopen("7532.in", "r", stdin);freopen("7532.out", "w", stdout);//原来的代码保持不变double a, b, r;int k;cin >> a >> b;k = int(a/b);r = a - b * k;printf("%g", r);//-------------fclose(stdin);fclose(stdout);return 0;
}