85 条题解
-
2
Lifi LV 10 @ 2019-08-04 13:37:07
按区间起点排序，逐个遍历区间合并，感觉有点贪心的意思，固定开始点，之后尽量吞并之后的区间使得区间尾尽量延长。
#include <iostream> #include <algorithm> using namespace std; typedef struct { int b,e; }qj; int n; qj qjlist[50000]; bool comp(qj a,qj b) { if(a.b==b.b) { return a.e>b.e; } else { return a.b<b.b; } } int main() { cin>>n; int i,b=-1,e; for(i=0;i<n;i++) { cin>>qjlist[i].b>>qjlist[i].e; } sort(qjlist,qjlist+n,comp); for(i=0;i<n;i++) { if(b==-1) { b=qjlist[i].b; e=qjlist[i].e; } else { if(qjlist[i].b<=e) { if(qjlist[i].e>e) { e=qjlist[i].e; } } else { cout<<b<<' '<<e<<endl; b=-1; i--; } } } cout<<b<<' '<<e<<endl; return 0; } -
2
排序+模拟
c++
#include<bits/stdc++.h>
using namespace std;
struct P{
int a,b;
bool operator <(const P &rdgs)const{
return(a<rdgs.a||a==rdgs.a&&b<rdgs.b);
}
}a[50002];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].a,&a[i].b);
sort(a+1,a+n+1);
/*for(int i=1;i<=n;i++)
printf("%d %d\n",a[i].a,a[i].b);*/
P d=a[1];
for(int i=2;i<=n;i++){
if(a[i].a>d.b){
printf("%d %d\n",d.a,d.b);
d=a[i];
}else
d.b=max(d.b,a[i].b);
}
printf("%d %d\n",d.a,d.b);
return 0;
}
-
0
#include <iostream>
#include <algorithm>
using namespace std;
struct c{
int start;
int endd;};
bool cmp(struct c a,struct c b){return a.start<b.start;
}
int n;
int main()
{cin>>n;
struct c p[n];
for(int i=0;i<n;i++){
cin>>p[i].start;
cin>>p[i].endd;
}
stable_sort(p,p+n,cmp);
int s=p[0].start,e=p[0].endd;
for(int i=1;i<n;i++){
if(p[i].start>=s&&p[i].start<=e){
if(p[i].endd>e){
e=p[i].endd;}else{
}
}else{
cout<<s<<" "<<e<<endl;s=p[i].start;
e=p[i].endd;}
}
cout<<s<<" "<<e<<endl;
return 0;
} -
0
#include<iostream> using namespace std; int main() { int q; cin >> q; long long *a = new long long[q]; long long *b = new long long[q]; for (int i = 0; i < q; i++) cin >> a[i] >> b[i]; for (int k = 1; k < q; k++) { for (int j = 0; j < q - k; j++) { if (a[j]>a[j + 1]) { swap(a[j], a[j + 1]); swap(b[j], b[j + 1]); } } } for (int i = 0; i < q - 1; i++) { if (a[i + 1] > b[i]) cout << a[i] << ' ' << b[i] << endl; else if (b[i + 1]>=b[i]) a[i + 1] = a[i]; else if (b[i + 1] < b[i]) { a[i + 1] = a[i]; b[i + 1] = b[i]; } } cout<<a[q - 1]<<' '<<b[q - 1]<<endl; return 0; } -
0
离散化题解
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int res[50005][2],n,pre,st,cnt; struct A { int l,r; }a[50005]; inline bool cmp(A x,A y) { return x.l==y.l?x.r<y.r:x.l<y.l; } void init() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&a[i].l,&a[i].r); } } void work() { sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++) { if(a[i].l>pre) { res[++cnt][1]=st; res[cnt][2]=pre; st=a[i].l;pre=a[i].r; } else { pre=max(a[i].r,pre); } if(i==n) { res[++cnt][1]=st; res[cnt][2]=pre; } } } void outit() { for(int i=2;i<=cnt;i++) { printf("%d %d",res[i][1],res[i][2]); if(i!=cnt) cout<<endl; } } int main() { init(); work(); outit(); return 0; } -
0
无需解释：
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<stack>
using namespace std;
int n,m,i=0,a,b,sum[2000001],flag=0,maxn=0;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a>>b;
if(b>maxn)
maxn=b;
a*=2,b*=2;
for(int i=min(a+1,b);i<=b;i++)
sum[i]=1;
}
for(int i=1;i<=maxn*2;i++)
{
if(sum[i]==0&&sum[i+1]==1)
{
if(i%2==1) i++;
cout<<i/2<<" ";
}
if(sum[i]==1&&sum[i+1]==0)
{
if(i%2==1) i++;
cout<<i/2<<endl;
}
}
return 0;
} -
0
sort排序+二分
#include<iostream>
#include<cstdio>
#include<string>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct node{
int a,b;
}a[50005];
int n,tot=0;
int q[50005],p[50005];
bool comp(const node &a,const node &b)
{
if(a.a!=b.a)return a.a<b.a;
return a.b<b.b;
}
inline void ef(int i){
int l=1,r=tot;
while(l<r)
{
int mid=l+r>>1;
if(a[i].a>p[mid])l=mid+1;
if(a[i].a<=p[mid])r=mid;
}
if(a[i].b>p[l])p[l]=a[i].b;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].a,&a[i].b);
}
sort(a+1,a+n+1,comp);
q[++tot]=a[1].a;
p[tot]=a[1].b;
for(int i=2;i<=n;i++)
{
if(a[i].a<=p[tot])ef(i);
else{
q[++tot]=a[i].a;
p[tot]=a[i].b;
}
}
for(int i=1;i<=tot;i++)
{
cout<<q[i]<<" "<<p[i]<<endl;
}
} -
0
#include <stdio.h> #include <stdlib.h> #define inf 0xffffff int l[50001],r[50001]; int cmp(const void *a,const void *b) { return (*(int *)a-*(int *)b); } int main() { int n,i,h=0; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d%d",&l[i],&r[i]); qsort(&l[1],n,sizeof(l[0]),cmp); qsort(&r[1],n,sizeof(r[0]),cmp); int ll=1,rr=1,tmp=0; r[n+1]=l[n+1]=inf; while(ll<=n||rr<=n) { if(l[ll]<=r[rr]) { if(h==0) tmp=l[ll]; h++; ll++; } else { h--; rr++; } if(h==0) printf("%d %d\n",tmp,r[rr-1]); //printf("%d %d\n",tmp,ll); } return(0); } -
0
chenjuncong LV 7 @ 2015-08-04 15:10:10
建议看线段覆盖，code vs，线段区间类问题集合
-
0
离散化经典题目
-
0
#include<cstdio>
#include<algorithm>
using namespace std;
struct Type{
int x,y;
}a[50001];
int n,l,r;
bool my_comp(const Type&a,const Type&b){
if (a.x<b.x) return 1;
if (a.x>b.x) return 0;
if (a.y<b.y) return 1;
return 0;
}
int main(){
//freopen("p1.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
sort(a+1,a+n+1,my_comp);
l=a[1].x;
r=a[1].y;
for(int i=2;i<=n;i++)
if (a[i].x>r){
printf("%d %d\n",l,r);
l=a[i].x;
r=a[i].y;
continue;
}
else r=max(r,a[i].y);
printf("%d %d",l,r);
return 0;
} -
0
program x1433;
var
a,b,c,d:array[1..50000] of longint;
i,j,k,l,n,m,x,y,t:longint;procedure js(l,r:longint);
var i,j,mid,p,mif:longint;
begin
i:=l;j:=r;mid:=a[(r+l)div 2];mif:=b[(l+r)div 2];
repeat
while (a[i]<mid)or((a[i]=mid)and(b[i]<mif)) do inc(i);
while(a[j]>mid)or((a[j]=mid)and(b[j]>mif)) do dec(j);
if i<=j then
begin
p:=a[i];a[i]:=a[j];a[j]:=p;
p:=b[i];b[i]:=b[j];b[j]:=p;
inc(i);dec(j);
end;
until i>j ;
if i<r then js(i,r);
if j>l then js(l,j);
end;
begin
readln(n);
for i:=1 to n do
readln(a[i],b[i]);
js(1,n);
t:=1;
c[1]:=a[1];
d[1]:=b[1];
for i:=2 to n do
if a[i]>d[t] then
begin
t:=t+1;
c[t]:=a[i];
d[t]:=b[i];
end
else
if b[i]>d[t] then
d[t]:=b[i];
for i:=1 to t do
writeln(c[i],' ',d[i]);
end. -
0
测试数据 #0: Accepted, time = 0 ms, mem = 1408 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1412 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1412 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1408 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1408 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1412 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 1408 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 1408 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1412 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 1408 KiB, score = 10
Accepted, time = 30 ms, mem = 1412 KiB, score = 100
代码
program exam1439;
var a,b,c,d:array[1..51000]of longint;
m,n,i,r,s,j,o,p,l:longint;
procedure js(l,r:longint);
var m,i,j,p:longint;
begin
i:=l; j:=r;
m:=b[(l+r)div 2];
repeat
while b[i]<m do inc(i);
while b[j]>m do dec(j);
if (i<=j) or((b[i]=b[j])and(a[i]>a[j])) then
begin
p:=a[i];a[i]:=a[j];a[j]:=p;
p:=b[i];b[i]:=b[j];b[j]:=p;
inc(i);dec(j);
end;
until i>j;
if l<j then js(l,j);
if i<r then js(i,r);
end;
begin
readln(s);
for i:=1 to s do
readln(a[i],b[i]);
for i:=1 to s do
if a[i]>b[i] then
begin
p:=a[i];a[i]:=b[i];b[i]:=p;
end; js(1,s);
l:=maxlongint; m:=1;
for i:=1 to s do
if a[i]<l then l:=a[i];
c[m]:=l;
for i:=2 to s do
begin
if a[i]>b[i-1] then
begin
j:=i;
while (a[j]>b[i-1])and(j<s+1) do
inc(j);
if j=s+1 then
begin
d[m]:=b[i-1];inc(m);c[m]:=a[i];
end;
end;
end; d[m]:=b[s];
for i:=1 to m do
writeln(c[i],' ',d[i]);
end. -
0
program _1439qujian;
var a,b,n,sum,i,max:longint;
s:array[1..1000001]of integer;
q:array[1..1000001]of boolean;
begin
readln(n);
max:=0;
for i:=1 to n do
begin
read(a,b);
if b>max then max:=b;
begin
inc(s[a]);
dec(s[b]);
if a=b then q[a]:=true;
end;
end;
sum:=0;
for i:=1 to max+1 do
begin
if (q[i]=true)and(sum=0) then begin write(i,' ',i);writeln;end
else begin
sum:=sum+s[i];
if (sum-s[i]=0)and(s[i]>0)then
write(i,' ')
else if(s[i]<0)and(sum=0)then
writeln(i);
end;
end;
end. -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms
#include
#include
#include
#include
int cmp(const void *a,const void *b)
{
return *(int *)a-*(int *)b;
}
main()
{int n,i,j=0;
scanf("%ld",&n);
int a[n],b[n];
for(i=0;i
Lifi
LV 10
@ 2019-08-04 13:37:07
