非洛谷题目，求神犇给个思路

题目总版

wula_miao @ 2024-10-30 20:12:31

有n颗星星，每个星星能被观测的时间范围为[s_i, t_i]，1 <= s_i <= t_i，在每一个整数时刻，都可以选择一个可观测星星进行拍摄(第i颗星星在s_i,t_i这两个时刻也可以被观测到) 现给n个星星的观测时间范围，问从时刻1开始，最多能拍摄到多少不同的星星？

第一行一个整数n(1<=n<=2*10^5)，表示星星的个数

接下来n行，每行两个正整数s_i, t_i(1<=s_i<=t_i<=10^9),表示可以在[s_i,t_i]内观测到该星星

输出：一个正整数，表示最多可以拍摄到的不同星星数

sample1
input:
4
1 1
1 2
2 2
2 3
output:
3
sample2:
input:
5
2 3
1 2
3 3
3 4
1 5
output:
5

个人用贪心做法分别按开始和结束时间进行排序都没做出来，做法是从时间1开始遍历，每次+1或跳到下一个星星的开始时间，以下是反例：

按结束时间贪心错:
6
1 4
4 4
2 5
5 5
1 6
6 6
实际能拍摄到6个，但结束贪心只能拍到4个
按开始时间贪心错误太明显就不写了

by c22j33c43 @ 2024-10-30 20:58:21

。。。。反例中实际不就是四个嘛，选第四个时刻拍的最多

by c22j33c43 @ 2024-10-30 20:59:24

第五时刻3个，第六时刻2个

by c22j33c43 @ 2024-10-30 21:07:14

等等，奇怪，题目问的是一个时刻内能拍的最多星星吗？（不然是什么）

by c22j33c43 @ 2024-10-30 21:08:52

哦，知道了

by c22j33c43 @ 2024-10-30 21:29:52

#include<bits/stdc++.h>
using namespace std;
int n,ans,an,p,rem[200002];
struct book{
    int s,t,l;
}q[200002];
inline bool cmp(book a,book b){
    return a.l<b.l;
}//先排范围小的，范围小的选择少 
void find(int k,int s){
    if(p==1) return;
    if(k==n+1){
        p=1;
        ans=max(s,ans);
        return;
    }//因为事先搞好了优先级，得到的一定是最优解 
    for(int i=q[k].s;i<=q[k].t;i++){
        if(rem[i]==0){
            rem[i]=1;
            find(k+1,s+1);
            rem[i]=0;
        }
    }//优先找空缺 
    for(int i=q[k].s;i<=q[k].t;i++) find(k+1,s);//没空才舍 
    return;
}
int main(){
    //freopen("1.in","r",stdin);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>q[i].s>>q[i].t;
        q[i].l=q[i].t-q[i].s+1;
    } 
    sort(q+1,q+n+1,cmp);//排序 
    find(1,0);//找最优解 
    cout<<ans;
    return 0;
}

by c22j33c43 @ 2024-10-30 21:30:46

给的样例都对，不知道能不能过

by c22j33c43 @ 2024-10-30 21:35:26

。。。那啥，我这有一道题，推广一下

https://www.luogu.com.cn/problem/U498123

想做就做

by c22j33c43 @ 2024-10-31 09:54:50

。。。。rem数组开小了，自己开大吧

by c22j33c43 @ 2024-10-31 10:15:15

#include<bits/stdc++.h>
using namespace std;
int n,ans,an,p,rem[100000002];//凉了，开不到10^9,当玩笑看吧
struct book{
    int s,t,l;
}q[200002];
inline bool cmp(book a,book b){
    return a.l<b.l;
}//先排范围小的，范围小的选择少 
void find(int k,int s){
    if(p==1) return;
    if(k==n+1){
        p=1;
        cout<<s;
        return;
    }//因为事先搞好了优先级，得到的一定是最优解 
    for(int i=q[k].s;i<=q[k].t;i++){
        if(p==1) return;//返回太慢了，再加一个
        if(rem[i]==0){
            rem[i]=1;
            find(k+1,s+1);
            rem[i]=0;
        }
    }//优先找空缺 
    find(k+1,s);//没空才舍 
    return;
}
int main(){
    freopen("4.in","r",stdin);
    freopen("4.out","w",stdout);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>q[i].s>>q[i].t;
        q[i].l=q[i].t-q[i].s+1;
    } 
    sort(q+1,q+n+1,cmp);//排序 
    find(1,0);//找最优解 
    return 0;
}