qq群推广引流免费网站,网站前端包括哪些,烟台网站建设seo,企业简介模板范文P2564 [SCOI2009]生日礼物
题意#xff1a;
n个彩珠#xff0c;k个种类#xff0c;分布在一个彩带上#xff0c;现在要选取彩带的一部分#xff0c;要求该部分包含所有种类的彩珠#xff0c;且长度尽可能短#xff0c;你能计算这个最短的长度吗#xff1f; 1≤N≤100…P2564 [SCOI2009]生日礼物
题意
n个彩珠k个种类分布在一个彩带上现在要选取彩带的一部分要求该部分包含所有种类的彩珠且长度尽可能短你能计算这个最短的长度吗 1≤N≤10000001≤K≤600≤珠子位置2{31}
题解
比赛时第一反应是尺取但是一看这个距离放弃了后来想可以先离散或者map距离因为种种原因都没做出现在赛后补题 实质用的是区间伸缩 因为珠子的位置范围很大但是珠子的数量有限所以我们完全可以枚举珠子的数量 我们给每种彩珠编号以及存下每种彩珠的坐标 然后根据坐标排序 然后就是区间伸缩我一直认为是尺取两个指针l和r分别指向左右两端的两种珠子在一半题中我们都会让指针指向距离的左右两端但是因为本题距离过长所以我们使其指向左右两端彩珠即第i个彩珠和第j个彩珠 左端l更新情况是如果第l个彩珠和第l-1个彩珠在一个位置那我们就l以l1个彩珠为新的起点 相当于我们以不同的彩珠作为左端点然后枚举右端点当num m时说明目前这个区间上有了所有的彩珠 u1s1我也将不大很明白就是把尺取距离变成尺取每种彩珠 详细看看代码把
代码
#includebits/stdc.h
typedef long long ll;
using namespace std;
inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
const int maxn1000008;
struct node{int pos;//位置 int id;//种类
}a[maxn];
int b[maxn];//用来统计每种彩珠的出现次数
bool cmp(node a,node b)
{return a.posb.pos;
}
int main()
{int n,k;cinnk;int tot0;for(int i1;ik;i){int t;cint;for(int j1;jt;j){cina[tot].pos;a[tot].idi;}}sort(a1,a1tot,cmp);int l1,r1;int num0;//记录当前彩带上有多少种彩珠b[a[l].id];//先将第一个彩珠记录 num;int sum1e9;//最后记录答案 while(lnrn){if(numk){summin(sum,a[r].pos-a[l].pos);//更新答案 b[a[l].id]--;if(b[a[l].id]0)num--;//离开l点l;if(ln)break;while(a[l].posa[l-1].pos)//如果移动后还是原来那个位置 {b[a[l].id]--;if(b[a[l].id]0)num--;l;if(ln)break;}}else {r;if(rn)break;b[a[r].id];if(b[a[r].id]1)num; while(a[r].posa[r1].pos){r;if(rn)break;b[a[r].id];if(b[a[r].id]1)num;}}} coutsum;
}
