题解 P3972 【[TJOI2014]电影评分】

· · 题解

在网上听人说这题暴力可过，本着no zuo no die的心态试了一发...

结果不仅过了，还跑得比香港记者还快，我甚至还没开氧气优化！

我将发动同学写此题，此题将成为一道省选红题

正解好像是平衡树?

upd:加点完全不必要的说明

id/fid记录每部电影存在数组里的编号/R操作给出的编号

Q:直接把所有电影存进数组排序即可

R:直接按题意模拟即可

C:fid转换编号直接按题意修改即可

直接暴力搞就好了

上代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ddf;
const int N=100000+10;
int id[N],fid[N],ac[N],tot,n;
ddf s[N];
struct node{
    ddf x;
    int y;
}a[N];
bool cmp(node a,node b){
    return a.x==b.x?a.y<b.y:a.x>b.x;
}
char b[16];
int main(){
    int x,y,z;
    ddf xp,yp,zp;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%s",b);
        if(b[0]=='Q'){
            scanf("%d",&x);
            for(int i=1;i<=tot;i++)a[i]=(node){s[i],i};
            sort(a+1,a+1+tot,cmp);
            printf("%d\n",id[a[x].y]);
        }
        else if(b[0]=='R'){
            int mx=0;
            scanf("%d%d",&x,&y);
            id[++tot]=x;
            fid[x]=tot;
            for(int i=1;i<=y;i++){
                scanf("%d",&z);
                mx=max(mx,ac[z]);
                ac[z]=tot;
            }
            s[tot]=s[mx];
        }
        else {
            scanf("%d%lf",&x,&xp);
            x=fid[x];
            s[x]=(s[x]+xp)/2;
        }
    }
    return 0;
}
/*
10
R 1 1 1
R 2 2 1 2
C 2 2
R 3 1 2
Q 1
C 3 2
C 1 5
Q 1
Q 2
Q 3
*/