UVALive – 4294 Shuffle 映射+取反+最大区间覆盖

Shuffle 映射+取反+最大区间覆盖

Source

UVALive - 4294

My Solution

题意：歌曲种数为s，记录的数量为n，然后给出这个n个记录，每s个歌会随机播放一遍，然后开始重新随机播放这s首歌，为未来可能在几个点进行一次新的循环。

映射+取反+最大区间覆盖
扫一遍数组，每次如果i - last[v[i]] < s，则点x必须是在这个区间里划分，然后新的循环会在kx之后出现，

所以把i和last[v[i]]映射到 [0, s) 里，
然后如果 (i % s) > (last[v[i]] % s) 则答案在区间[(last[v[i]] % s), (i % s))里，取反以后
是答案不可能在 [0, (last[v[i]] % s) ) 和[(i % s), s)里。
如果 (i % s) < (last[v[i]] % s) 则答案在区间 [0, (i % s)) 和[(last[v[i]] % s), s)里，取反以后
答案不可能在区间[(i % s), (last[v[i]] % s))里
然后跑一遍把所有的不可能区间搞出来，然后就是最大区间覆盖问题，ans = s - 最大区间覆盖
复杂度 略大于O(n) 远小于 O(nlogn)

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 8;
const int INF = 1e9 + 7;
int v[maxn], last[maxn];

struct interval{
    int l, r;
    interval(int x, int y) : l(x), r(y) {}
};

vector val;

inline bool cmp(const interval& a, const interval& b)
{
    if(a.l != b.l) return a.l < b.l;
    else return a.r < b.r;
}

int main()
{
    #ifdef LOCAL
    freopen("h.txt", "r", stdin);
    //freopen("h.out", "w", stdout);
    #endif // LOCAL
    //ios::sync_with_stdio(false); cin.tie(0);

    int T, s, n, i, j, sz, ans;
    scanf("%d", &T);
    while(T--){
        val.clear();
        memset(last, -1, sizeof last);
        scanf("%d%d", &s, &n);
        for(i = 0; i < n; i++){ cin >> v[i];
            if(last[v[i]] != -1){
                if(i - last[v[i]] < s){ if((i % s) > (last[v[i]] % s)){
                        val.push_back(interval(0, (last[v[i]] % s)));
                        val.push_back(interval((i % s), s));
                    }
                    else{
                        val.push_back(interval((i % s), (last[v[i]] % s)));
                    }
                }
            }
            last[v[i]] = i;
        }

        sort(val.begin(), val.end(), cmp);
        sz = val.size();
        ans = s;
        for(i = 0; i < sz; i++){
            if(i + 1 < sz && val[i].r >= val[i + 1].l) {
                val[i + 1].l = val[i].l; val[i].l = INF; val[i+1].r = max(val[i].r, val[i + 1].r);
            }
            else{
                ans -= val[i].r - val[i].l;
            }
        }
        printf("%dn", ans);
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx