刷题记录

Operating System 优先队列+贪心
很好的一道贪心的题目，首先我们肯定知道重复的我们就可以不用动它，一旦内存中不存在需要展示的了，看已经在队列里面的数，谁的相同的下一个数离的最远就替换掉谁。因此我们需要维护每个位置对应的值以及下次出现在哪个位置。那么假设是值仅出现一次，那默认为无穷远。

//#pragma GCC optimize(1)
//#pragma GCC optimize(2)
//#pragma GCC optimize(3,"Ofast","inline")

#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define int long long
#define ll __int128
#define double long double
#define lowbit(x) (x&(-x))
#define log(x) (31^__builtin_clz(x))
#define endl '\n'

typedef pair<int,int>PII;
typedef pair<double,double>PDD;
typedef tuple<double,double,double>TDDD;
typedef tuple<int,int,int>TIII;

const int N = 2e5+10;
const int mod = 1e9+7 , P = 131;
const double PI = acos(-1);
const double eps = 1e-8;

mt19937_64 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());//随机数

int read(){
    char c=0;
    int res=0;
    int f=1;
    while(!(c>='0'&&c<='9')){
        if(c=='-'){
            f=-f;
        }
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        res=(res<<3)+(res<<1)+c-'0';
        c=getchar();
    }
    return res*f;
}

void write(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(char(x%10+'0'));
}

int n,m,q;
int w[N];
bool vis[N];
int ne[N],last[N];

void solve(){
    while(cin>>n>>m>>q){
        for(int i=1;i<=q;i++)cin>>w[i];

        memset(vis,0,sizeof vis);
        memset(ne,0,sizeof ne);
        memset(last,0x3f,sizeof last);

        for(int i=q;i;i--){
            ne[i]=last[w[i]],last[w[i]]=i;
        }

        priority_queue<PII>pq;

        int ans=0,tmp=0;

        for(int i=1;i<=q;i++){
            if(vis[w[i]])tmp++;
            if(pq.size()<n+tmp&&!vis[w[i]]){
                ans++;
                vis[w[i]]=1;
            }else if(pq.size()==n+tmp&&!vis[w[i]]){
                ans++;
                vis[pq.top().y]=false;
                vis[w[i]]=true;
                pq.pop();
            }
            pq.push({ne[i],w[i]});
        }
        cout<<ans<<endl;
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T;
    T=1;
    while(T--)solve();

#ifdef PURPLE
    cerr<<fixed<<setprecision(10)<<1.0*clock()/CLOCKS_PER_SEC<<endl;
#endif
    return 0;
}

网络优化 贪心+优先队列
总的思路就是先把i前面的左区间所在的下标放入小顶堆中，而后把右区间的中最小的先用掉。

//#pragma GCC optimize(1)
//#pragma GCC optimize(2)
//#pragma GCC optimize(3,"Ofast","inline")

#include<bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define int long long
#define ll __int128
#define double long double
#define lowbit(x) (x&(-x))
#define log(x) (31^__builtin_clz(x))
#define endl '\n'

typedef pair<int,int>PII;
typedef pair<double,double>PDD;
typedef tuple<double,double,double>TDDD;
typedef tuple<int,int,int>TIII;

const int N = 2e5+10;
const int mod = 1e9+7 , P = 131;
const double PI = acos(-1);
const double eps = 1e-8;

mt19937_64 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());//随机数

int read(){
    char c=0;
    int res=0;
    int f=1;
    while(!(c>='0'&&c<='9')){
        if(c=='-'){
            f=-f;
        }
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        res=(res<<3)+(res<<1)+c-'0';
        c=getchar();
    }
    return res*f;
}

void write(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(char(x%10+'0'));
}

int n,m;
struct E{
    int l,r,v;
    bool operator<(const E& t)const{
        if(l!=t.l)return l<t.l;
        if(r!=t.r)return r<t.r;
        return v<t.v;
    }
};

struct cmp{
    bool operator()(const E& a,const E& b){
        if(a.r!=b.r){
            return a.r>b.r;
        }else{
            return a.v>b.v;
        }
    }
};
//总的思路就是先把i前面的左区间所在的下标放入小顶堆中，而后把右区间的中最小的先用掉
//这就是贪心的思路
void solve(){
    while(cin>>n>>m){
        vector<E>w;

        for(int i=0;i<m;i++){
            int l,r,v;
            cin>>l>>r>>v;
            w.push_back({l,r,v});
        }

        sort(w.begin(),w.end());

        priority_queue<E,vector<E>,cmp>q;//小顶堆

        int cur=0,ans=0;

        for(int i=1;i<=n;i++){
            while(cur<m&&w[cur].l<=i){
                q.push(w[cur]);
                cur++;
            }
            
            while(q.size()&&(q.top().r<i||!q.top().v)){
                q.pop();
            }
            if(!q.size())continue;
        
            E t=q.top();
            q.pop();
            t.v--;
            ans++;
            q.push(t);
        }
        cout<<ans<<endl;
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int T;
    T=1;
    while(T--)solve();

#ifdef PURPLE
    cerr<<fixed<<setprecision(10)<<1.0*clock()/CLOCKS_PER_SEC<<endl;
#endif
    return 0;
}