弹幕是现今网络视频常见的评论方式,能够反映一个视频的火爆程度。假设某个时间一共有N条弹幕,每条弹幕i的持续时间为两个整数表示的时间区间(a[i],b[i]),我们定义弹幕数量最多的一个时间段为最精彩时段,求一个视频的最精彩时段。
弹幕是现今网络视频常见的评论方式,能够反映一个视频的火爆程度。假设某个时间一共有N条弹幕,每条弹幕i的持续时间为两个整数表示的时间区间(a[i],b[i]),我们定义弹幕数量最多的一个时间段为最精彩时段,求一个视频的最精彩时段。
第一行整数N,代表弹幕的条数,其中90%的 N < 1000000, 60%的N < 10000
第二行到第N+1行,是两个整数(a[i],b[i]),代表每条弹幕的开始时间和结束时间, 请注意(a[i],b[i])是全开区间, 并且a[i], b[i] < 100
M行,每行两个整数(c,d),M是答案个数,(c,d)代表视频最精彩时段的开始时间和结束时间,并且M个答案区间互不重叠。答案请按照开始时间从小到大输出。请注意每行结尾应包含换行符,包括最后一行。
3 0 4 1 4 2 3
2 3
4 1 2 3 4 2 3 4 5
1 2 2 3 3 4 4 5
3 0 2 2 4 1 3
1 2 2 3
请注意由于区间定义为开区间,所以答案为(1,2)和(2,3)
#include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) int a[100] = {0}; int b[100] = {0}; int t[100] = {0}; int N,m; int s,e; int main() { scanf("%d",&N); rep(i,0,N) { scanf("%d%d",&s,&e); a[s]++;b[e]++; } t[0] = m = a[0]; rep(i,1,100) { t[i] = t[i-1] + a[i] - b[i]; if (t[i] > m) m = t[i]; } for (int i = 0;i < 100; i++) { if (t[i] == m) { printf("%d", i); while (t[i] == m && b[i+1] == 0) i++; printf(" %d\n", i+1); } } }
import sys n = int(sys.stdin.readline()) be_list=[] mp = [[0]*101 for i in range(101)] lp = [[0]*101 for i in range(101)] pos = [False for i in range(101)] m = 0 def cmpt(be0,be1): if(be0[0]!=be1[0]): if be0[0]<be1[0]: return -1 else: return 1 elif(be0[1]!=be1[1]): if be0[1]<be1[1]: return -1 else: return 1 else: return 0 for i in range(n): line = sys.stdin.readline() lines = line.split() be =( int(lines[0]), int(lines[1]) ) be_list.append(be) pos[be[1]] = True for i in range(be[0],be[1]): mp[i][i+1]=mp[i][i+1]+1 if mp[i][i+1]>m: m = mp[i][i+1] be_list.sort(cmp=cmpt) i = be_list[0][0] j = i + 1 while j < be_list[-1][1]: if mp[i][j] == m : while mp[j][j+1] == m and pos[j] == False and j < be_list[-1][1]: j = j+1 lp[i][j] = m i = j j = j +1 else: i = j j = j + 1 for i in range(100): for j in range(100): if lp[i][j] == m: print '%d %d' %(i,j)
#include<bits/stdc++.h> using namespace std; #define ll long long bool cmp(pair<int,int> A,pair<int,int> B) { if(A.first!=B.first) return A.first<B.first; else return A.second<B.second; } int main() { int n; cin>>n; vector<pair<int,int> > vec(n); map<int,bool> pos; ll m=INT_MIN; ll mp[105][105]={0};//一定要记得初始化为0,否则内存中的数是一个随机数。 for(int i=0; i<n; i++) { cin>>vec[i].first>>vec[i].second; pos[vec[i].second]=true; for(int j=vec[i].first; j<vec[i].second; j++) {//标记每一个小区间 mp[j][j+1]++; if(mp[j][j+1]>m) m=mp[j][j+1]; } } sort(vec.begin(),vec.end(),cmp); /*for(int i=0;i<vec.size();i++){ cout<<vec[i].first<<" "<<vec[i].second<<endl; }*/ int b=vec[0].first,e=b+1; while(e<vec[vec.size()-1].second){ if(mp[b][e]==m){ while(mp[e][e+1]==m&&pos[e]==false&&e<vec[vec.size()-1].second){ mp[b][e+1]=m; mp[e][e+1]=0; mp[b][e]=0; e++; } b=e; e++; } else{ b=e; e++; } } //cout<<m<<endl; for(int i=vec[0].first;i<vec[vec.size()-1].second;i++){ for(int j=i+1;j<=vec[vec.size()-1].second;j++){ if(mp[i][j]==m) cout<<i<<" "<<j<<endl; //if(mp[i][j]!=0) cout<<i<<" "<<j<<" "<<mp[i][j]<<endl; } } return 0; }