NOIP 2016 D2T 2 - 지렁이

문제 설명
이 문제 에서 우 리 는 기호 * 8970 ° c * 8971 ° 로 c 를 아래로 정리 하 는 것 을 표시 할 것 이다. 예 를 들 어 * 8970 ° 3.0 * 8971 ° = * 8970 ° 3.1 * 8971 ° = * 8970 ° 3.9 * 8971 ° = 3.귀뚜라미 나 라 는 최근 에 지렁이 가 재 해 를 입 었 다!옆집 벼룩 나라 의 벼룩 도 지렁이 들 을 잡 을 수 없 었 습 니 다. 귀뚜라미 왕 은 어 쩔 수 없 이 신 도 를 불 러 지렁이 를 없 애 달라 고 했 습 니 다.귀뚜라미 나라 에는 현재 모두 n 마리 의 지렁이 가 있다.모든 지렁이 는 길 이 를 가지 고 있 습 니 다. 우 리 는 i 번 째 지렁이 의 길 이 를 ai (i = 1, 2, n) 로 설정 하고 모든 길이 가 비 마이너스 정수 (즉 길이 가 0 인 지렁이 가 존재 할 수 있 습 니 다) 를 확보 합 니 다.매 초 에 신 도 는 모든 지렁이 중에서 가장 긴 한 마 리 를 정확하게 찾 아 반 으로 썬 다.신도 손 으로 지렁이 를 자 르 는 위 치 는 상수 p (0 < p < 1 의 유리 수 를 만족 시 키 는 것) 에 의 해 결정 된다. 이 지렁이 의 길 이 는 x 이 고 신도 손 은 이 를 각각 floor * 8970 ° px * 8971 ° 와 x - * 8970 ° px * 8971 ° 의 지렁이 로 자른다.특히 이 두 수의 하나 가 0 이면 이 길이 가 0 인 지렁이 도 보존 된다.그 밖 에 방금 생 긴 두 마리 의 새 지렁이 를 제외 하고 나머지 지렁이 의 길 이 는 모두 q (비 마이너스 상수) 를 증가 할 것 이다.귀뚜라미 왕 은 이것 이 장기 적 인 계획 이 아니 라 는 것 을 알 고 있 었 습 니 다. 지렁이 는 점점 많아 질 뿐만 아니 라 점점 길 어 지기 때 문 입 니 다.귀뚜라미 왕 은 홍 황 의 힘 을 가 진 신비 한 인물 에 게 도움 을 청 하기 로 결 정 했 습 니 다. 하지만 구원병 은 m 초가 걸 려 야 도착 할 수 있 습 니 다.구체 적 으로 그 는 m 초 동안 매 초 에 잘 린 지렁이 가 잘 리 기 전의 길이 (m 개 수) 를 알 고 싶 어 한다.m 초 후 모든 지렁이 의 길이 (n + m 개수).귀뚜라미 국왕 은 당연히 어떻게 하 는 지 알 지!그러나 그 는 당신 을 시험 하고 싶 어 합 니 다.u, v, t 는 모두 정수 이다.당신 은 스스로 p = u / v 를 계산 해 야 합 니 다.

3 7 1 1 3 1
3 3 2

샘플 출력:

3 4 4 4 5 5 6
6 6 6 5 5 4 4 3 2 2

사고 분석 & 코드:
1. 먼저 set 가 생각 나 서 set 를 사 용 했 습 니 다. 그래서 지적 장애 코드 를 썼 습 니 다. CE, set 는 교체 기 만 사용 할 수 있 기 때 문 입 니 다.
지능 장애 코드

#include 
#include 
#include 
using namespace std;
int main(){
    set<int> s;
    int n,m,q,u,v,t;
    cin>>n>>m>>q>>u>>v>>t;
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        s.insert(a);
    }
    double p=u/v;
    for(int i=1;i<=m;i++){
        int t2=s[n+m-2];
        if(i%t==0)cout<2]<<" ";
        s.erase(s[m+n-2]);
        for(int i=m+n-3;i>=0;i--)s[i]+=q;
        s.insert(int(p*t2));
        s.insert(t2-int(p*t2));
    }
    cout<for(int i=1;i<=n;i++){
        if(i%t==0)cout<return 0;
}

set 는 작은 것 부터 큰 것 까지 정렬 되 고 set 의 교체 기 는 it + 변 수 를 실행 할 수 없습니다. it + 연산 자 만 사용 할 수 있 기 때문에 저 는 구조 체 를 썼 습 니 다. 다시 불 러 옵 니 다.

struct QY{
    int l;
    bool operator < (const QY& b)const{
        if(this->l>b.l)return true;
        return false;
    }
};

드디어 크 고 작은 서열 이 생 겼 습 니 다. 하지만 set 의 문 제 는 집합 이 중복 되 지 않 는 다 는 것 입 니 다. 그래서 하나의 맵 을 써 서 하나의 길이 가 몇 번 나 타 났 는 지 기록 하 였 습 니 다. 만약 횟수 가 0 이면 set 에서 요 소 를 삭제 합 니 다. 그래서 다음 과 같 습 니 다.

void myinsert(QY a){
    if(!cnt.count(a.l)){cnt[a.l]=0;s.insert(a);}
    cnt[a.l]++;
    return;
}

void myerase(QY a){
    cnt[a.l]--;
    if(cnt[a.l]==0){cnt.erase(a.l);s.erase(a);}
    return;
}

그 다음 에 시 뮬 레이 션 이지 만 map 가 느 려 요.
WA + TLE 코드 (set + map)

#include 
#include 
#include 
#include 
using namespace std;

map<int,int>cnt;
struct QY{
    int l;
    bool operator < (const QY& b)const{
        if(this->l>b.l)return true;
        return false;
    }
};
set s;

void myinsert(QY a){
    if(!cnt.count(a.l)){cnt[a.l]=0;s.insert(a);}
    cnt[a.l]++;
    return;
}

void myerase(QY a){
    cnt[a.l]--;
    if(cnt[a.l]==0){cnt.erase(a.l);s.erase(a);}
    return;
}

int main(){
    int n,m,q,u,v,t;
    cin>>n>>m>>q>>u>>v>>t;
    double p=u/v;

    for(int i=1;i<=n;i++){
        QY tmp;
        scanf("%d",&tmp.l );
        myinsert(tmp);
    }

    set::iterator it;


    for(int i=1;i<=m;i++){
    it=s.begin();
    QY tmp=*it;
    if(i%t==0)printf("%d ",tmp.l);
    myerase(tmp);
    for(it=s.begin();it!=s.end();it++){
        QY tmp2=*it;
        tmp2.l +=q;
    }
    tmp.l=t*p;
    myinsert(tmp);
    tmp.l=t-tmp.l;
    myinsert(tmp);
    }

    cout<for(int i=1;i<=n+m;it++){
        QY tmp=*it; 
        for(int j=0;jif(i%t==0){printf("%d ",tmp.l);}
        }
    }
    return 0;
}

map 느 려 서 다른 방법 을 찾 아야 합 니 다. 1. pair 2. 구조 체 에 나타 난 횟수 를 추가 하지만 두 가지 방법 중 하 나 는 set 에서 찾 으 면 찾 을 수 없습니다. 찾 을 때 나타 난 횟수 를 모 르 기 때 문 입 니 다. s. count ()괄호 안에 있 는 데이터 형식 은 구조 체 나 pair 이 고 매개 변수 수가 모두 안 되 기 때문에 set 는 안 됩 니 다. set 와 유사 한 것 을 생각 하지만 데 이 터 는 중복 할 수 있 습 니까? 우선 대기 열! 하지만 문 제 는 우선 대기 열 에 지침 이 없다 는 것 입 니 다. 교체 기 방식 으로 데 이 터 를 수정 할 수 없습니다 (지렁이 길이 증가) 물론 타임 스탬프 (입대 시간) 를 추가 할 수 있 습 니 다., lazy 태그 처럼 사용 시 추가 (현재 시간 - 타임 스탬프) * q)그런데 시간 스탬프 는 어떻게 저장 합 니까? 이번 에는 맵 도 안 됩 니 다. 길이 가 똑 같 아서 시간 스탬프 가 다 를 수 있 습 니 다! 그래서 안 됩 니 다. 그리고 방법 도 있 습 니 다. 예 를 들 어 시간 이 i 일 때 입 대 를 해 야 합 니 다. 그러면 이 입 대 를 해 야 할 데 이 터 를 i * q 를 빼 면 팀 을 나 갈 때 저 는 그 가 처음에 입 대 했 고 팀 을 나 갈 시간 * q 를 더 하면 감 소 된 부분 을 상쇄 할 수 있 습 니 다.그리고 후발 자 데 이 터 는 작 아서 시간 지연 으로 인 한 팀 오류 에 대해 고려 할 필요 가 없습니다. 우선 대기 열의 상수 가 크 면 카드 가 걸 립 니 다. 최대 80 점 (O2 최적화 도) 입 니 다. 이것 은 우리 가 아래 의 3 대기 열 을 사용 할 수 있 는 방법 입 니 다.
우선 대기 열 코드

#include 
#include 
#include 
#include 
using namespace std;
priority_queue<int> que;
int m,n,q,u,v,t,add=0;
int main(){
cin>>n>>m>>q>>u>>v>>t;
for(int i=1;i<=n;i++){
    int tmp;
    scanf("%d",&tmp);
    que.push(tmp);
}
for(int i=1;i<=m;i++){
    int tmp=que.top();
    que.pop();
    tmp+=add;
    int a=(long long)tmp*u/v;
    int b=tmp-a;
    que.push(a-add-q);
    que.push(b-add-q);
    if(i%t==0)printf("%d ",tmp);
    add+=q;
}
printf("
");
for(int i=1;i<=n+m;i++){
    if(i%t==0)printf("%d ",que.top()+add);
    que.pop();
}
return 0;
}

그리고 방법: 두 마리 의 지렁이 길이 가 각각 x, y, 그리고 x > y 라 고 가정 합 니 다. 그러면 제목 의 x 에 따라 반드시 먼저 잘 립 니 다. 그래서 우 리 는 y 가 x 가 잘 린 후에 i 초 에 잘 린 다 고 가정 합 니 다. x 가 x1 과 x2 로 잘 렸 다 고 가정 하면 y 는 y1 과 y2 로 잘 립 니 다. x1 > x2 y1 > y2 가 마음대로 썼 다 고 가정 하면 이 관 계 는 어떻게 써 도 x1 > y1, x2 > y2 가 될 수 있 습 니 다. 그래서 우 리 는 3 개의 대기 열 을 열 어 자 르 지 않 은 qs 를 저장 합 니 다.(이미 큰 것 에서 작은 것 으로 정렬) q1 저장 p * x, q2 저장 x - p * x; 앞에서 얻 을 수 있 는 모든 대기 열 은 단조 로 운 (여기 서 큰 것 에서 작은 것) 이 므 로 매번 3 개의 더미 의 최대 요 소 를 모 의 하면 시간 스탬프 와 같은 것 을 만 들 수 있 습 니 다.
3 대기 열 코드

#include 
#include 
#include 
#include 
#include 

using namespace std;

queue<int>qq,q1,q2;
int n,m,q,u,v,t,tmp[100050],add=0;

int cmp(int a,int b){return a>b;}

int getfront(queue<int> &q){
    if(q.empty())return -0x3f3f3f3f;
    return q.front()+add;
}

int compare_each_front(){
    int a=getfront(qq),b=getfront(q1),c=getfront(q2);
    int maxn=max(a,max(b,c));
    if(maxn==a) qq.pop();
    else if(maxn==b) q1.pop();
    else if(maxn==c) q2.pop();
    return maxn;
}

int main(){
    cin>>n>>m>>q>>u>>v>>t;
    for(int i=0;iscanf("%d",&tmp[i]);
    sort(tmp,tmp+n,cmp);
    for(int i=0;ifor(int i=1;i<=m;i++,add+=q){
        int tmp=compare_each_front();
        int a=(long long)tmp*u/v;
        int b=tmp-a;
        q1.push((int)a-add-q);
        q2.push((int)b-add-q);
        if(i%t==0)cout<" ";
    }
    cout<for(int i=1;i<=n+m;i++){
        int tmp=compare_each_front();   
        if(i%t==0)printf("%d ",tmp);
    }
    return 0;

}