P2564 [SCOI2009]生日禮物

題意：

n個彩珠，k個種類，分布在一個彩帶上，現在要選取彩帶的一部分，要求該部分包含所有種類的彩珠，且長度盡可能短，你能計算這個最短的長度嗎？
1≤N≤1000000，1≤K≤60，0≤珠子位置<2^{31}

題解：

比賽時第一反應是尺取，但是一看這個距離放棄了，后來想可以先離散？或者map距離，因為種種原因都沒做出，現在賽后補題
實質用的是區間伸縮
因為珠子的位置范圍很大，但是珠子的數量有限，所以我們完全可以枚舉珠子的數量
我們給每種彩珠編號以及存下每種彩珠的坐標
然后根據坐標排序
然后就是區間伸縮（我一直認為是尺取），兩個指針l和r，分別指向左右兩端的兩種珠子，在一半題中我們都會讓指針指向距離的左右兩端，但是因為本題距離過長，所以我們使其指向左右兩端彩珠（即第i個彩珠和第j個彩珠）
左端l更新情況是：如果第l個彩珠和第l-1個彩珠在一個位置，那我們就l++，以l+1個彩珠為新的起點
相當于我們以不同的彩珠作為左端點，然后枚舉右端點，當num == m時，說明目前這個區間上有了所有的彩珠
（u1s1我也將不大很明白，就是把尺取距離變成尺取每種彩珠）
詳細看看代碼把

代碼：

#include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=1000008; struct node{int pos;//位置 int id;//種類 }a[maxn]; int b[maxn];//用來統計每種彩珠的出現次數 bool cmp(node a,node b) {return a.pos<b.pos; } int main() {int n,k;cin>>n>>k;int tot=0;for(int i=1;i<=k;i++){int t;cin>>t;for(int j=1;j<=t;j++){cin>>a[++tot].pos;a[tot].id=i;}}sort(a+1,a+1+tot,cmp);int l=1,r=1;int num=0;//記錄當前彩帶上有多少種彩珠b[a[l].id]++;//先將第一個彩珠記錄 num++;int sum=1e9;//最后記錄答案 while(l<=n&&r<=n){if(num==k){sum=min(sum,a[r].pos-a[l].pos);//更新答案 b[a[l].id]--;if(b[a[l].id]==0)num--;//離開l點l++;if(l>n)break;while(a[l].pos==a[l-1].pos)//如果移動后還是原來那個位置 {b[a[l].id]--;if(b[a[l].id]==0)num--;l++;if(l>n)break;}}else {r++;if(r>n)break;b[a[r].id]++;if(b[a[r].id]==1)num++; while(a[r].pos==a[r+1].pos){r++;if(r>n)break;b[a[r].id]++;if(b[a[r].id]==1)num++;}}} cout<<sum; }

總結

以上是生活随笔為你收集整理的P2564 [SCOI2009]生日礼物的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。