文档章节

【SCOI 2009】生日礼物

LOI_xczhw
 LOI_xczhw
发布于 2016/10/30 09:57
字数 252
阅读 4
收藏 0

我只会打尺取法……怎么破

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN = 1e6 + 5;
int tong[60 + 5];
bool a[MAXN][60 + 5];
int n,k;
vector <int> lsh;
int where(int x)
{
    return lower_bound(lsh.begin(),lsh.end(),x) - lsh.begin();
}
int cqf()
{
    int l = 0,r = -1,minn = 2147483647;
    int ans = 0;
    while(true)
    {
        int maxn = lsh.size();
        while(ans < k && r < maxn)
        {
            r++;
            for(int i = 1;i <= k;i ++)
            {
                if(!a[r][i])
                    continue;
                if(!tong[i])
                    ans++;
                tong[i]++;
            }
        }
        if(ans < k)
            return minn;
        minn = min(minn,lsh[r] - lsh[l]);
        for(int i = 1;i <= k;i ++)
        {
            if(!a[l][i])
                continue;
            tong[i] --;
            if(!tong[i])
                ans--;
        }
        l++;
    }
    return 0;
}
vector <int> z[60 + 5];//x[i] 第i种珠子有这么多个 
int m,x;
int main()
{
    scanf("%d %d",&n,&k);
    for(int i = 1;i <= k;i ++)
    {
        scanf("%d",&m);
        for(int j = 1;j <= m;j ++)
        {
            scanf("%d",&x);
            z[i].push_back(x);
            lsh.push_back(x);
        }
    }
    sort(lsh.begin(),lsh.end());
    unique(lsh.begin(),lsh.end());
    vector<int>::iterator it;
    for(int i = 1;i <= k;i ++)
        for(it = z[i].begin();it != z[i].end();it++)
            a[where(*it)][i] = true;
    printf("%d\n",cqf());
    return 0;
}

看的黄学长博客里的单调队列好神啊……
大家去看吧,我也不敢转载……2333

© 著作权归作者所有

LOI_xczhw
粉丝 1
博文 79
码字总数 42567
作品 0
莱芜
私信 提问
长大后,送朋友礼物更困难了……

1 浏览百度时,看到一个话题讨论,说如果朋友送了不喜欢的东西你该怎么办? 发帖人说道:她不喜欢“玉”,也不是说不喜欢,主要原因是因为不懂“玉”的好坏和价格。 比起玉她更直接喜欢纯白金...

随心摆文
01/30
0
0
写一个简单的Java代码当生日礼物!

怎么写一个简单的Java代码当生日礼物呢?呵呵,求例子!

zhuogaopeng
2012/11/26
1K
1
NKOJ 4151 (TJOI 2016&HEOI 2016)字符串(后缀数组+倍增+主席树)

【Tjoi2016&Heoi2016】字符串 问题描述 佳媛姐姐过生日的时候,她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为n的字符串s,和m个问题。佳媛姐姐必...

Mogician_Evian
2017/12/13
0
0
HTC G10连接电脑失败

昨天收到的生日礼物,老高兴了。 是一部HTC G10手机。 可是今天一到公司,想下载点应用,结果发现和电脑无法连接。 驱动是自动下载的, 亲们,gui qiu解决方案。

jeffsui
2012/02/16
1K
7
2012年社交电商购物网站TOP6

1、蘑菇街 蘑菇街官方网站,中国最大的女性购物社区,2000万女性会员一起发现时尚至IN的扮美单品,交流最新最热的时尚穿搭,分享在各大购物网站的网购经验。 网址:http://www.mogujie.com/ 2、美...

kitstlei
2013/01/19
377
8

没有更多内容

加载失败,请刷新页面

加载更多

nginx常用命令

# cd /usr/local/nginx/sbin 查看版本 # ./nginx -v 查看进程 # ps -ef | grep nginx 查看nginx端口号 # ss -lnput | grep nginx 启动 # ./nginx 关闭 # ./nginx -s stop 重新加载配置文件 ......

行者终成事
14分钟前
4
0
002-docker的网络设置和数据管理

Docker 网络设置 docker会创建一个桥接网卡[docker 0],docker有两种映射方式,一种是随机映射,一种是指定映射 生产场景一般不用随机映射 随机映射的好处是端口由docker分配,不会冲突 安装n...

侠客行之石头
18分钟前
4
0
Rust学习笔记一 数据类型

写在前面 我也不是什么特别厉害的大牛,学历也很低,只是对一些新语言比较感兴趣,接触过的语言不算多也不算少,大部分也都浅尝辄止,所以理解上可能会有一些偏差。 自学了Java、Kotlin、Python、...

MusiCodeXY
21分钟前
4
0
Java 脚本引擎入门

Java Script Engine Java 脚本引擎可以将脚本嵌入Java代码中,可以自定义和扩展Java应用程序,自JDK1.6被引入,基于Rhino引擎,JDK1.8后使用Nashorn引擎,支持ECMAScript 5,但后期还可能会换...

阿提说说
今天
5
0
05.深入浅出索引(下)

在下面这个表T中,如果我们执行select * from T where k between 3 and 5,需要执行几次树的搜索操作,会扫描多少行? mysql> create table T ( id int primary key, k int not null default...

scgaopan
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部