[bzoj 1293][SCOI2009] 生日礼物
2018-06-17 20:54:44来源:未知 阅读 ()
传送门
题目:
Description
Input
Output
Sample Input
1 5
2 1 7
3 1 3 8
Sample Output
HINT
有多种方案可选,其中比较短的是1~5和5~8。后者长度为3最短。
【数据规模】
对于50%的数据, N≤10000;
对于80%的数据, N≤800000;
对于100%的数据,1≤N≤1000000,1≤K≤60,0≤彩珠位置<2^31。
题解:
写法大意:单调队列
sort一遍保证位置的单调性,开一个pos数组存第i种彩带最后出现的位置,出队的时候判断一下那个元素的位置是否与pos数组相同即可(不同才能出队)
就样例来模拟一波:
6 3
1 5
2 1 7
3 1 3 8
进行排序以后的f数组:
f[i].x | 2 | 3 | 3 | 1 | 2 | 3 |
f[i].y | 1 | 1 | 3 | 5 | 7 | 8 |
(pos数组要先初始化为-1)
(len要初始化为f[n].y-f[1].y,即最坏的情况(否则会有5个点挂掉(luogu会,bzoj没试过)))
当i=1时
pos[f[i].x]为-1,那么f[i]入队,队列中的珠子多了一个了,cnt++
更新pos[f[i].x]的值为f[i].y
开始出队操作:
当队头head<=队尾i且队头的元素所在位置f[head].y!=该位置珠子最后出现的位置(即pos[f[head].x])时就可以出队了!
最后更新一下答案:
当cnt(队列内珠子种数)=k(珠子种数)时就可以更新答案了!
len=min(len,f[i].y-f[head].y)
这样从头枚举到尾就好了,时间复杂度(nlogn)(排序需要nlogn的时间复杂度)
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll int
#define min(x,y) x<y?x:y
inline void read(ll &x){
x=0;ll f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
x*=f;
}
using namespace std;
#define N 1000010
struct node{ll x,y;}f[N];
//x表示所属彩珠类型,y表示w位置
ll n,k,len,pos[N];
bool cmp(node x,node y){return x.y<y.y;}
int main(){
read(n);read(k);ll a,b=0;
for(ll i=1;i<=k;i++){
read(a);pos[i]+=a;
for(ll j=1;j<=a;j++){
read(f[++b].y);
f[b].x=i;
}
}
sort(f+1,f+n+1,cmp);
len=f[n].y-f[1].y;ll head=1,cnt=0;
memset(pos,-1,sizeof(pos));
for(ll i=1;i<=n;i++){
if(pos[f[i].x]==-1)cnt++;
pos[f[i].x]=f[i].y;
while(head<=i&&f[head].y!=pos[f[head].x])head++;
if(cnt==k&&f[i].y-f[head].y<len)len=f[i].y-f[head].y;
}
printf("%d",len);
return 0;
}
转载请注明出处哈:http://www.cnblogs.com/henry-1202/p/8666497.html
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- bzoj3569 DZY Loves Chinese II 2020-05-25
- bzoj4036 [HAOI2015]按位或 2020-04-26
- 「BZOJ4173」数学 2020-01-15
- bzoj3944 Sum 2019-12-25
- BZOJ1008: [HNOI2008]越狱(快速幂) 2019-08-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash