luogu2564 [SCOI2009]生日礼物
2024-08-24 21:01:48
排序枚举左端点，则右端点必定不降
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
struct Node{
int pos, val;
}nd[1000005];
int n, k, cnt[63], uu, vv=0, rig=0, re=0, ans=0x3f3f3f3f;
void rn(int &x){
x = 0;
char ch=getchar();
while(ch<'0' || ch>'9') ch = getchar();
while(ch>='0' && ch<='9'){
x = x * 10 + ch - '0';
ch = getchar();
}
}
bool cmp(Node x, Node y){
return x.pos<y.pos;
}
int main(){
rn(n); rn(k);
for(int i=1; i<=k; i++){
rn(uu);
for(int j=1; j<=uu; j++){
rn(nd[++vv].pos);
nd[vv].val = i;
}
}
sort(nd+1, nd+1+vv, cmp);
for(int i=1; i<=n; i++){
while(re<k && rig<n){
rig++;
if(++cnt[nd[rig].val]==1)
re++;
}
if(re==k)
ans = min(ans, nd[rig].pos-nd[i].pos);
if(--cnt[nd[i].val]==0) re--;
}
cout<<ans<<endl;
return 0;
}
当然也可以用滑动窗口的思想做，就是比较慢
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
struct Node{
int pos, val;
}nd[1000005];
int n, k, cnt[63], uu, vv=0, lev=1, rig=0, a[1000005];
void rn(int &x){
x = 0;
char ch=getchar();
while(ch<'0' || ch>'9') ch = getchar();
while(ch>='0' && ch<='9'){
x = x * 10 + ch - '0';
ch = getchar();
}
}
bool cmp(Node x, Node y){
return x.pos<y.pos;
}
bool check(int lim){
memset(cnt, 0, sizeof(cnt));
lev = 1, rig = 0;
int re=0;
for(int i=1; i<=n; i++){
while(lev<=rig && nd[a[lev]].pos<nd[i].pos-lim){
if(--cnt[nd[a[lev]].val]==0) re--;
lev++;
}
a[++rig] = i;
if(++cnt[nd[i].val]==1) re++;
if(re==k) return true;
}
return false;
}
int main(){
rn(n); rn(k);
for(int i=1; i<=k; i++){
rn(uu);
for(int j=1; j<=uu; j++){
rn(nd[++vv].pos);
nd[vv].val = i;
}
}
sort(nd+1, nd+1+vv, cmp);
int l=0, r=nd[vv].pos, mid, ans=0;
while(l<=r){
mid = (l + r) >> 1;
if(check(mid)){
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
cout<<ans<<endl;
return 0;
}
最新文章
- 第一章Android系统移植与驱动开发概述--读书笔记
- 怎样实现了捕获应用中的日志在android开发中
- 分布式消息系统：Kafka
- Linux vsftp配置本地用户
- 算法与数据结构之选择排序（C语言）
- dlib库使用
- Java基础之写文件——使用Formatter对象加载缓冲区（UsingAFormatter)
- listview某一项不可点击
- POJ 3422 Kaka's Matrix Travels (K取方格数：最大费用流)
- 从实验室搬到宿舍后可以上QQ但打不开网页
- 解决statusStrip控件上的项目不能靠右对齐的问题
- Big Clock
- QQ空间自动发广告解决方法
- ASP.NET 开发学习视频教程大全（共800集）
- W - Bitset（第二季水）
- php网站共享session方法（相同一级域名）
- Android的第二次增加SurfaceView基本使用
- windows全系列激活脚本-改良版.cmd
- jspf与jsp的区别
- 【转载】ASP.NET中Server.MapPath方法获取网站根目录总结