BZOJ 1293: [SCOI 2009] 생일 선물 (낙 곡 P2564)
4457 단어 낙 곡BZOJ데이터 구조 --- 단조 대기 열블 로그 칼럼
BZOJ 제목 전송 문 낙 곡 제목 전송 문
노 입 난이도 인 것 같 아 요.
모든 구슬 을 x 순 으로 배열 하 다.각 구슬 에 대해 계산 하여 그것 을 왼쪽 끝 점 으로 하 는 컬러 테이프 의 길 이 를 최소 화 합 니 다.왼쪽 에서 오른쪽으로 단조 로 운 대기 열 을 유지 하면 됩 니 다.
코드:
#include
#include
#include
#include
#define N 1000005
#define F inline
using namespace std;
struct p{ int c,x; }a[N];
int n,k,l,r,ans=0x7fffffff,m,num,q[N],c[65];
F char readc(){
static char buf[100000],*l=buf,*r=buf;
if (l==r) r=(l=buf)+fread(buf,1,100000,stdin);
if (l==r) return EOF; return *l++;
}
F int _read(){
int x=0,f=1; char ch=readc();
while (!isdigit(ch)) { if (ch=='-') f=-1; ch=readc(); }
while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=readc();
return x*f;
}
F bool cmp(p a,p b){ return a.xx; }
int main(){
n=_read(),k=_read();
for (int i=1;i<=k;i++)
for (int m=_read(),j=1;j<=m;j++)
a[++num].c=i,a[num].x=_read();
sort(a+1,a+n+1,cmp),q[l=r=1]=m=1,c[a[1].c]++;
while (m!=k){
q[++r]=r,c[a[r].c]++;
if (c[a[r].c]==1) m++;
}
ans=min(ans,a[r].x-a[l].x);
while (1){
if (!(--c[a[l].c])) m--; l++;
while (m!=k&&r<=n){
q[++r]=r,c[a[r].c]++;
if(c[a[r].c]==1) m++;
}
if (r>n) break;
ans=min(ans,a[r].x-a[l].x);
}
return printf("%d
",ans),0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
BZOJ3930: [CQOI2015] 선택거의 짠 물고기일 거야.. 처음에 제목 yy에 대해 정확할 것 같고 복잡도 계산이 안 되는 검색을 했는데 잘 안 되는 것 같아서 DP를 생각하고 정확해 보이는 DP를 생각해서 끊었어요.그럼 용납하고 싶다......설...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.