P1803 凌乱的yyy / 线段覆盖
  E3ku1Hi0Uh1i 2023年11月02日 90 0


​传送门​

P1803 凌乱的yyy / 线段覆盖_#include

思路:

先按照结束时间从小到大排序,然后选择第一个比赛,接着标记所有与第一个比赛时间重复的比赛,并选择未标记比赛中的第一个比赛,然后重复上述流程。

#include<bits/stdc++.h>
using namespace std;
struct node{
int sta;
int end;
}tim[1000010];
bool vis[1000010];
bool cmp(node a, node b)
{
return a.end < b.end;
}
int main()
{
int n;
scanf("%d",&n);
for(int i = 1; i <= n; i++)
{
scanf("%d%d",&tim[i].sta,&tim[i].end);
vis[i] = true;
}
sort(tim+1, tim+1+n,cmp);
int ans = 0;
for(int i = 1; i <= n; i++)
{
if(vis[i])
{
ans++;
for(int j = i; j <=n; j++)
{
if((tim[j].sta >= tim[i].sta && tim[j].sta < tim[i].end) || (tim[j].end > tim[i].sta && tim[j].sta < tim[i].end))
{
vis[j] = false;
}
}
}
}
printf("%d\n",ans);
}


【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 2023年11月08日 0

暂无评论

推荐阅读
  4WdcduV19eWs   2023年11月02日   65   0   0 ios#includeios#include
  4WdcduV19eWs   2023年11月02日   62   0   0 ios#includeios#include
  4WdcduV19eWs   2023年11月02日   67   0   0 ios#includeios#include
  4WdcduV19eWs   2023年11月02日   54   0   0 ios#includeios#include
  4WdcduV19eWs   2023年11月02日   43   0   0 ios#includeios#include
  4WdcduV19eWs   2023年11月02日   66   0   0 ios#includeios#include
  4WdcduV19eWs   2023年11月02日   89   0   0 ios#includeios#include
  4WdcduV19eWs   2023年11月02日   51   0   0 ios#includeios#include
  4WdcduV19eWs   2023年11月02日   78   0   0 #includelinuxlinux#include
  5b99XfAwWKiH   2023年11月12日   36   0   0 githubC++openrmcfish
E3ku1Hi0Uh1i