社区讨论

求助,离散化60pts,WA at #1,2,3,4

P3740[HAOI2014] 贴海报参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lz9da5tu
此快照首次捕获于
2024/07/31 12:48
2 年前
此快照最后确认于
2024/07/31 14:25
2 年前
查看原帖
CPP
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
vector<int> post;
set<int> st;
int wall[2005]; 
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) {
        int ta,tb;
        scanf("%d%d",&ta,&tb);
        ta=max(ta,1);
        tb=min(tb,n);
        post.push_back(ta);
        post.push_back(tb);
    }
    vector<int> tmp(post);
    sort(tmp.begin(),tmp.end());
    tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
    for(int i=0;i<2*m;i++) {
        post[i]=lower_bound(tmp.begin(),tmp.end(),post[i])-tmp.begin();
    }
    for(int i=1;i<=m;i++) {
        int l=2*i-2,r=2*i-1;
        for(int j=post[l];j<=post[r];j++) {
            wall[j]=i;
        }
    }
    bool flag=0;
    for(int i=0;i<2*m;i++) {
        st.insert(wall[i]);
        if(!wall[i]) flag=1;
    }
    printf("%d\n",st.size()-flag);
    return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...