P8086 『JROI-5』Music

· · 题解

官方题解。

A

考虑顺序处理每一条记录，如何处理两个约束条件是本题的核心。

首先对于 t\leq1 可以在读入的时候直接判断处理，忽略即可。

cin >> x >> t;
if(t <= 1) continue;

那么如何判断这首歌之前是否被累加过呢？一种做法是记录下所有的记录，扫描之前的判断是否累计过。

cin >> x0 >> t0;
if(t0 <= 1) continue;
bool f = 1;
for(int j = 1; j <= cnt; j ++){
    if(x[j] == x0) f = 0;
}
if(f) {
    ans += t0; x[++ cnt] = x0; t[cnt] = t0;
}

容易发现上述做法的时间复杂度是 \mathcal{O}\left(n^2\right) 的，可以通过 40\% 的数据。那么我们何不开一个桶，记录某首歌是否又被听过？

cin >> x >> t;
if(t <= 1) continue;
if(vis[i]) continue;
else {
    ans += t;vis[x] = 1;
}

上述做法的时间复杂度是 \mathcal{O}\left(n\right) 的，可以通过 100\% 的数据。