当前位置: 首页 > 编程日记 > 正文

[SCOI2009]生日礼物

这道题很容易看出是一道单调队列题。

首先我们根据珠子的位置排序。

然后按顺序枚举一个个珠子。

如果该种珠子没有出现过标记上它的位置,如果出现过修改并打上当前位置。当所有珠子都出现后,将当前位置减去打标记位置最小的一个即为当前解。

可以证明正确性。

显然选择珠子越靠后越好。

最小位置的查找要$O(K)$,所以复杂度为$O(NK)$。

这道题$K$比较小,该复杂度能过。但当$K$较大时会超时。

我们充分运用单调队列的性质,牺牲空间换取时间。

具体做法就是开一个数组记录第$i$个珠子是否在标记中,然后用一个指针$P$记录位置最小的珠子。

珠子只会从前往后打上标记,所以当取消珠子的标记时,根据需要向后移动$P$指针直到再一次指向位置最小的珠子即可。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define re register
 6 #define rep(i, a, b) for (re int i = a; i <= b; ++i)
 7 #define repd(i, a, b) for (re int i = a; i >= b; --i)
 8 #define maxx(a, b) a = max(a, b);
 9 #define minn(a, b) a = min(a, b);
10 #define LL long long
11 #define inf (1 << 30)
12 
13 inline int read() {
14     int w = 0, f = 1; char c = getchar();
15     while (!isdigit(c)) f = c == '-' ? -1 : f, c = getchar();
16     while (isdigit(c)) w = (w << 3) + (w << 1) + (c ^ '0'), c = getchar();
17     return w * f;
18 }
19 
20 const int maxn = 1e6 + 5, maxk = 60 + 5;
21 
22 struct Ball {
23     int k, p;
24 } A[maxn];
25 bool cmp(Ball a, Ball b) {
26     return a.p < b.p;
27 }
28 
29 int loc[maxk], N, K, tag[maxn];
30 
31 int main() {
32     N = read(), K = read();
33 
34     int P = 0;
35     rep(i, 1, K) {
36         int T = read();
37         rep(x, 1, T) A[++P] = (Ball){i, read()};
38     }
39     sort(A+1, A+N+1, cmp);
40     P = 0;
41     int cnt = 0, ans = (1<<31)-1;
42     memset(tag, 0, sizeof(tag));
43     rep(i, 1, N) {
44         tag[loc[A[i].k]] = 0;
45         if (!loc[A[i].k]) cnt++;
46         loc[A[i].k] = i;
47         tag[loc[A[i].k]] = 1;
48         while (!tag[P]) P++;
49         if (cnt == K) minn(ans, A[i].p - A[P].p);
50     }
51     printf("%d", ans);
52     return 0;
53 }

转载于:https://www.cnblogs.com/ac-evil/p/10350916.html

相关文章:

.Net(c#) 通过 Fortran 动态链接库,实现混合编程

c# 与 Fortran 混合编程解决方案主要有两种&#xff1a;1. 进程级的交互&#xff1a;在 Fortran 中编译为控制台程序&#xff0c;.Net 调用&#xff08;System.Diagnostics.Process&#xff09;&#xff0c;然后使用 Process 的 StandardOutput 属性读取控制台输出内容&#xf…

11关于集成测试

集成测试的必要性 前言集成测试集成测试模式和方法总结前言 差之毫厘,失之千里。 集成测试 单元测试的目的是确认软件单元能够满足所规定的要求,将一些单元按一定的要求合成在一起就组成了集合体。集成测试的目的是确认集合体能够正确地满足所规定的要求,集成后的各软件单…

Maven 手动添加第三方依赖包及编译打包和java命令行编译JAVA文件并使用jar命令打包...

一&#xff0c;实例:新建了一个Maven项目,在eclipse中通过 build path –> configure path….将依赖包添加到工程中后&#xff0c;eclipse不报错了。但是用Maven命令 mvn clean compile 时出错如下&#xff1a; 原因是在eclipse中添加了 exteneral jar后&#xff0c;还需要在…

Codeforces Educational round 58

Ediv2 58 随手AK.jpgD 裸的虚树&#xff0c;在这里就不写了 E 傻逼贪心&#xff1f;这个题过的比$B$都多.jpg #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <cstdlib> #include <queue> #includ…

VC 单文档程序 隐藏程序及任务栏图标

1 在APP类InitInstance()里 注释掉&#xff1a; m_pMainWnd->ShowWindow(SW_SHOW); 2 CMainFrame::OnCreate(LPCREATESTRUCT lpCreateStruct)里加 AfxGetApp()->m_nCmdShow SW_HIDE; 3 隐藏任务栏图标&#xff1a; ModifyStyleEx(WS_EX_APPWINDOW,WS_EX_TOOLWINDOW…

12 集成测试方法之大棒集成方法

大棒集成方法大棒集成方法总结大棒集成方法 大棒集成方法先是对每一个子模块进行测试&#xff08;单元测试阶段&#xff09;&#xff0c;然后将所有模块一次性的全部集成起来进行集成测试。如图&#xff0c;先分别对A、B、C、D、E、F、G模块进行单元测试&#xff0c;然后按照设…

phonegap+emberjs+python手机店发展,html5实现本地车类别~

商城开发项目&#xff0c;现在需要做出APP&#xff0c;无奈出场前android但不是很精通。最后选择phonegap实现app。 由于之前办理购物车分为登陆和登陆后两种情况&#xff0c;登录前必须充分利用本地存储。而基于phonegap本地存储的发展是使用Html5的localstorage功能实现。特分…

世上最伟大的十个公式,1+1=2排名第七,质能方程排名第五

英国科学期刊《物理世界》曾让读者投票评选了“最伟大的公式”&#xff0c;最终榜上有名的十个公式既有无人不知的112&#xff0c;又有著名的Emc2&#xff1b;既有简单的-圆周公式&#xff0c;又有复杂的欧拉公式…… 从什么时候起我们开始厌恶数学&#xff1f;这些东西原本如此…

20位程序员关于求职的疑问,以及我给出的参考答案

作者&#xff1a;陆小凤首发&#xff1a;公众号【程序员江湖】阅读本文大概需要 6 分钟。前几天发了一条朋友圈对于求职小伙伴们提出的问题&#xff0c;我进行了收集整理&#xff0c;统一反馈。也许这20个问题也是你们遇到的问题&#xff0c;所以趁着年前赶紧把它发出来。以下2…

14 集成测试方法之自底向上集成方法

自底向上集成方法前言自底向上集成方法前言 集成测试方法没有好坏之分&#xff0c;只有哪个更适合。 自底向上集成方法 自底向上集成方法是从调用的底层开始逐级的向上集成&#xff0c;每测试完一个族群就将其挂到上一层的模块上。这种集成方法的特点是不需要写桩函数&#x…

JavaScript Document

document:文档对象 document.getElementById();//根据ID获取元素对象 document.getElementsByTagName();//根据标签名获取元素对象数组 document.getElementsByClassName();//根据类名获取元素对象数组 document.getElementsByName();//根据名字获取元素对象数组 document.crea…

effective C++ 读书笔记(11-28)

1: RAII 资源获得时机便是初始化时机 典型应用&#xff1a; 智能指针&#xff01; 2&#xff1a; 为什么 auto_ptr 指针复制之后 原指针就会变成NULL &#xff1a; 多分指针指向它 会被析构多次 delete 函数会多次调用 3&#xff1a; 我要再次留心 stl容器的数据结构 与 特性…

15 三明治集成方法和混合策略集成方法

三明治集成方法和混合策略集成方法 前言三明治集成方法混合策略集成方法总结前言 关于集成测试方法今天我们再学习两个方法,三明治集成方法和混合策略集成方法。 三明治集成方法 采用三明治方法的优点是:它将自顶向下和自底向上的集成方法有机地结合起来,不需要写桩函数,…

产品经理和程序员的爱恨情仇

产品经理跪求程序员&#xff0c;程序员跪求程序成功上线&#xff01;前几天纯银V在微博上发了一条微博「很多人吐槽“人人都是产品经理”这句话&#xff0c;其实在我看来&#xff0c;这句话的正确理解是“人人都应该学习产品经理的思维方式&#xff0c;来提升自己的专业能力”&…

DES加密算法安全性评估

DES加密算法应用误区 DES算法具有极高安全性&#xff0c;到目前为止&#xff0c;除了用穷举搜索法对DES算法进行攻击外&#xff0c;还没有发现更有效的办法。而56位长的密钥的穷举空间为256&#xff0c;这意味着如果一台计算机的速度是每一秒种检测一百万个密钥&#xff0c;则它…

css3伪元素选择器before 和 after 的使用

:before 的作用, 在子元素的最前面, 添加一个伪元素, 伪元素内容通过 content 控制,可以在content属性中写入文本内容&#xff0c;但是通常为空字符串。 :after 的作用, 在子元素的最后面, 添加一个伪元素, 伪元素内容通过 content 控制,可以在content属性中写入文本内容&#…

16 系统测试之功能测试

功能测试前言功能测试总结前言 系统测试一般要使系统软件运行于真实的硬件环境中&#xff0c;其更倾向于软硬件结合的测试。在本专题中主要介绍系统测试中的功能测试和性能测试。其他测试类型在本专题中咱不展开讲&#xff0c;会在以后的专题中详细说。 功能测试 对于功能测试…

TinyMCE的使用-安装

TinyMCE安装非常简单&#xff0c;它可以被初始化为<form>标签中的<textarea>&#xff0c;当提交表单时&#xff0c;TinyMCE编辑器的内容将作为<form>表单的一部分被提交。 步骤1&#xff1a;下载TinyMCE并将其放在网站服务器目录 下载TinyMCE将得到的zip包加…

查看存储过程死锁的存储过程

create proc p_lockinfokill_lock_spid bit1, --是否杀掉死锁的进程,1 杀掉, 0 仅显示show_spid_if_nolock bit1 --如果没有死锁的进程,是否显示正常进程信息,1 显示,0 不显示asdeclare count int,s nvarchar(1000),i intselect ididentity(int,1,1),标志,进程IDspid,线程IDkp…

离群点检测算法-基础概念

定义&#xff1a; Hawkins给出的离群点的本质性定义&#xff1a;离群点是数据集中偏离大部分数据的数据&#xff0c;由于偏离其它数据太多&#xff0c;使人怀疑这些数据的偏离并非由随机因素产生&#xff0c;而是产生于完全不同的机制。 大致分类&#xff1a; 一例分析步骤&am…

17 性能测试

性能测试 前言性能测试性能测试的目标总结前言 系统级性能测试是验证系统做的好不好,进行性能测试的前提条件是系统做的是对的。 性能测试 系统级性能测试是为了发现系统性能问题或获取系统性能相关指标而进行的测试。一般在真实环境、特定负载条件下,通过工具模拟实际软件…

关于mysql archive存储引擎-专门存储审计和日志数据

来源:http://60.29.242.49/?p60 政府还有一个让数据库专家摊上更多事情的职能&#xff0c;就是安全控制和数据审计。 那些管理着海量数据仓库的企业官员常常得回答诸如“何人何时修改了什么”或者“何人何时查看了什么”这样的提问。那些拥有数以千计的员工&#xff0c;开展着…

使用bitblt提高GDI+绘图的效率(转)

最近在做使用GDI绘制K线界面发现传统的GDI绘制方式效率比较低&#xff0c;根本无法满足K线界面及时刷新的速度要求。 所以做了个GDI绘制图形界面的试验&#xff0c;改试验主要在一个600600的区域内每隔10MS绘制6060个点&#xff0c;每隔10MS改变其颜色&#xff0c;并记录每次绘…

Bruck:一个Web界面布局原型设计框架\n

Bruck是一个面向网页设计师的新型lo-fi原型系统&#xff0c;让设计师可以快速为客户构建响应式且易于访问的布局原型。设计师可以通过组合多达25个Web组件来建立各种布局原型。设计师还可以在Bruck提供的在线Playground中实时可视化组合布局。Bruck可以生成屏幕阅读器可访问和响…

白盒测试方法之语句覆盖测试

语句覆盖测试 概念需求示例测试用例分析设计测试用例脚本语句覆盖情况总结概念 语句覆盖法的基本思想是设计若干测试用例,运行被测程序,使程序中的每个可执行语句至少被执行一次。 需求示例 程序源代码如下: void func(int a, int b, double c

每天学习Linux(3)---pwd命令

Linux中用 pwd 命令来查看”当前工作目录“的完整路径。 简单得说&#xff0c;每当你在终端进行操作时&#xff0c;你都会有一个当前工作目录。 在不太确定当前位置时&#xff0c;就会使用pwd来判定当前目录在文件系统内的确切位置。 1&#xff0e;命令格式&#xff1a; pwd […

恢复Opera11.50地址栏的下拉列表按钮

恢复Opera11.50地址栏的下拉列表按钮 我觉得新版本里取消这个功能很蛋痛. -------------------------------------------------- http://www.stormcn.cn/post/1066.html Opera11.50的地址栏从外观上已经默认取消了下拉列表的点击按钮&#xff0c;就是那个在地址栏最右边的倒三角…

大数据推荐(个性化推荐)

大数据推荐分享。三场讲座系统的讲解了关于基于大数据的个性化推荐的体系和针对模型的探索。作为讲师主讲了关于个性化推荐的一些流程和算法。 转载于:https://www.cnblogs.com/wenBlog/articles/10364415.html

白盒测试方法之条件覆盖测试

条件覆盖测试 概念需求示例测试用例分析设计测试用例脚本条件覆盖情况总结概念 条件覆盖的基本思想是设计若干测试用例,执行被测程序以后,要使每个判断中每个条件的可能取值至少满足一次。 这里要强调的是每个判断中的每一个条件,即使是同一条件,但在不同的判断中也需要分…

第三波精品Android源码袭来!免费下载

今天又汇总了一些源码供大家免费下载学习&#xff01;1.Android实现NewQuickAction快捷菜单NewQuickAction能根据点击事件发生的坐标来显示一个快捷菜单&#xff0c;比如点击位置在靠近底部&#xff0c;则弹出的菜单出现在点击位置的下面&#xff0c;反之&#xff0c;则出现在上…