P2564 [SCOI2009]生日礼物 贪心
2024-08-28 01:53:50
题意
有n个珠子,包括k中颜色,找出长度最小的一个区间,使得这个区间中包含所有的颜色。
思路
把n个珠子按照位子排序,然后维护每个珠子最右边能到的位子就行了。
#include <algorithm>
#include <iterator>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cassert> /* ⊂_ヽ
\\ Λ_Λ 来了老弟
\('ㅅ')
> ⌒ヽ
/ へ\
/ / \\
レ ノ ヽ_つ
/ /
/ /|
( (ヽ
| |、\
| 丿 \ ⌒)
| | ) /
'ノ ) Lノ */ using namespace std;
#define lson (l , mid , rt << 1)
#define rson (mid + 1 , r , rt << 1 | 1)
#define debug(x) cerr << #x << " = " << x << "\n";
#define pb push_back
#define pq priority_queue typedef long long ll;
typedef unsigned long long ull;
//typedef __int128 bll;
typedef pair<ll ,ll > pll;
typedef pair<int ,int > pii;
typedef pair<int,pii> p3; //priority_queue<int> q;//这是一个大根堆q
//priority_queue<int,vector<int>,greater<int> >q;//这是一个小根堆q
#define fi first
#define se second
//#define endl '\n' #define boost ios::sync_with_stdio(false);cin.tie(0)
#define rep(a, b, c) for(int a = (b); a <= (c); ++ a)
#define max3(a,b,c) max(max(a,b), c);
#define min3(a,b,c) min(min(a,b), c); const ll oo = 1ll<<;
const ll mos = 0x7FFFFFFF; //
const ll nmos = 0x80000000; //-2147483648
const int inf = 0x3f3f3f3f;
const ll inff = 0x3f3f3f3f3f3f3f3f; //
const int mod = 1e9+;
const double esp = 1e-;
const double PI=acos(-1.0);
const double PHI=0.61803399; //黄金分割点
const double tPHI=0.38196601; template<typename T>
inline T read(T&x){
x=;int f=;char ch=getchar();
while (ch<''||ch>'') f|=(ch=='-'),ch=getchar();
while (ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
return x=f?-x:x;
} inline void cmax(int &x,int y){if(x<y)x=y;}
inline void cmax(ll &x,ll y){if(x<y)x=y;}
inline void cmin(int &x,int y){if(x>y)x=y;}
inline void cmin(ll &x,ll y){if(x>y)x=y;} /*-----------------------showtime----------------------*/ const int maxn = 1e6+;
pll a[maxn];
ll d[];
int main(){
int n,k,tot=;
scanf("%d%d", &n, &k);
for(int i=; i<=k; i++){
int num; scanf("%d", &num);
for(int j=; j<=num; j++) {
int x; scanf("%d", &x);
a[++tot].fi = x;
a[tot].se = i;
}
}
sort(a +, a++tot);
ll ans = 1ll<<;
for(int i=; i<=tot; i++){
d[a[i].se] = a[i].fi;
ll mx = , flag = , mn = 1ll<<; for(int j=; j<=k; j++){
mx = max(mx, d[j]);
mn = min(mn, d[j]);
if(d[j] == ) flag = ;
}
if(flag) ans = min(ans, mx - mn);
}
printf("%lld\n", ans);
return ;
}
最新文章
- Access数据导入SQLServer2008R2
- sql中保留到小数点后两位以及非空判断赋值为零
- VS2010 断点无效肿么办?
- Oracle数据库作业-1
- 快速理解RequireJs
- led.c驱动框架
- php---tp框架---表单验证
- paxos 算法原理学习
- git - 1.基础
- SQL Update
- 解决angular ui-grid 中添加input date修改日期
- c groups
- 方向导数,梯度和梯度下降之BGD,SGD
- java 实现Word或Excel 转Pdf
- 最长上升子序列LIS(51nod1134)
- audio video 控制播放和停止
- JAVAWEB 一一 Sturts2+ibatis(框架,Sturts2,用action代替servlet)
- SSM_CRUD新手练习(6)分页后台控制器编写
- nginx 代理之修改header 的HOST,实现代理转代理
- 从零自学Java-4.使用字符串来交流
热门文章
- 二、PyTorch 入门实战—Variable(转)
- centos7主机间免密登录、复制文件
- 蘑菇街工程师常用的Linux命令!
- iOS Xcode6 新建OC Category文件
- 关于input[type=&#39;checkbox&#39;]全选的问题
- 统一流控服务开源:基于.Net Core的流控服务
- Python连载30-多线程之进程&;线程&;线程使用举例
- C#将图片转换成字符画
- 物联网时代-跟着Thingsboard学IOT架构-HTTP设备协议及API相关限制
- Kali Linux无法访问网络的问题