1 条题解

  • 0
    @ 2024-11-25 19:54:03

    对于这道题,当你所将要使用的魔法已经存在于书中,你就可以直接使用,否则需要花费一点魔法值将该魔法存入书中,若之前存满,则删去最早存的。

    题目虽然很长,但是题并不难。 我们只需要一个桶来储存魔法书中目前存放的魔法,同时定义两个指针来对于需要进行存放和删除的魔法进行记录。

    #include<bits/stdc++.h>
    #define int long long
    #define pii pair<int,int>
    #define endl '\n'
    using namespace std;
    const int mod = 1e9 + 7, inf = 1e18, N = 2e5 + 5;
    int a[N];//数组a用来存放魔法书放过的魔法
    void solve() {
        int m, n;
        cin >> m >> n;
        map<int,int> mp;
        int l = 1, r = 0;
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            if (mp[x] == 0) {//若魔法书中没有
                if (r - l + 1 >= m) {//判断魔法书中储存的魔法书是否大于书的最大页数
                    mp[a[l++]] = 0;//将最早储存的魔法删除
                }
                a[++r] = x;//储存新的魔法在a数组中
                mp[x] = 1;//将新的魔法放入魔法书
                ans++;
            }
        }
        cout << ans << endl;
    }
    
    signed main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr),cout.tie(nullptr);
        int T = 1;
        // cin >> T;
        while(T--) {
            solve();
        }
        return 0;
    }
    
    • 1

    信息

    ID
    1074
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    递交数
    58
    已通过
    14
    上传者