ADV-199線分と点
2503 ワード
問題の説明
n個の点とm個の区間があり、点と区間の端点はすべて整数であり、点aと区間[b,c]については、a>=bかつa<=cであれば、点aが区間[b,c]を満たすと称する.
最小の点のサブセットを求めて、すべての区間が満たされるようにします.
入力フォーマット
1行目の2つの整数n m
次のn行は行ごとに整数で、点の座標を表します.
次のm行は行ごとに2つの整数で、区間の範囲を表します.
出力フォーマット
無解出力-1のようなすべての区間を満たす点数を最小限に抑える行を出力します.
サンプル入力
5 5
2
6
3
8
7
2 5
3 4
3 3
2 7
6 9
サンプル出力
2
データ規模と約定
1<=n,m<=10000
0<=点と区間の座標<=50000
C
C++
n個の点とm個の区間があり、点と区間の端点はすべて整数であり、点aと区間[b,c]については、a>=bかつa<=cであれば、点aが区間[b,c]を満たすと称する.
最小の点のサブセットを求めて、すべての区間が満たされるようにします.
入力フォーマット
1行目の2つの整数n m
次のn行は行ごとに整数で、点の座標を表します.
次のm行は行ごとに2つの整数で、区間の範囲を表します.
出力フォーマット
無解出力-1のようなすべての区間を満たす点数を最小限に抑える行を出力します.
サンプル入力
5 5
2
6
3
8
7
2 5
3 4
3 3
2 7
6 9
サンプル出力
2
データ規模と約定
1<=n,m<=10000
0<=点と区間の座標<=50000
C
#include
typedef struct x
{
int l;
int r;
}line;
int main()
{
int n,m;
scanf("%d %d",&n,&m);
int num[10005];
line map[10005];
int i,j;
for(i=0;i=map[j].r)
{
map[i]=map[--m];
i--;
break;
}
else if(map[i].l>=map[j].l&&map[i].r<=map[j].r)
{
map[j]=map[--m];
j--;
}
}
}
for(i=0;imap[j].r)break;
while(num[i]<=map[j].r&&i=map[j].l&&j
C++
# include
# include
# include
using namespace std;
int vis[10010];
struct segment{
int begin;
int end;
};
struct node{
int cur;
int num;
};
struct node s1[50010];
struct segment s2[10010];
int compare2(struct segment a, struct segment b){
if(a.begin!=b.begin){
return a.begin=j&&!vis[k]){
s1[j].num++;
}
else{
break;
}
}
if(s1[j].num>max){
max=s1[j].num;
cur=j;
}
}
}
count++;
for(k = i+1; k <= m; k++){
if(s2[k].begin<=cur){
vis[k]=1;
}
else{
break;
}
}
}
}
printf("%d", count);
return 0;
}