首页 > 试题广场 >

弹幕

[编程题]弹幕
  • 热度指数:267 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 48M,其他语言96M
  • 算法知识视频讲解

弹幕是现今网络视频常见的评论方式,能够反映一个视频的火爆程度。假设某个时间一共有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个答案区间互不重叠。答案请按照开始时间从小到大输出。请注意每行结尾应包含换行符,包括最后一行。
示例1

输入

3
0 4
1 4
2 3

输出

2 3
示例2

输入

4
1 2
3 4
2 3
4 5

输出

1 2
2 3
3 4
4 5
示例3

输入

3
0 2
2 4
1 3

输出

1 2
2 3

说明

请注意由于区间定义为开区间,所以答案为(1,2)和(2,3)
#include <iostream>
using namespace std;
int main()//弹幕时间最长区间输出
{
    int n;
    cin >> n;
    int *p1 = new int[n];
    int *p2 = new int[n];
    int pc[100] = { 0 };
    int pd[100] = { 0 };
    int i;
    int r_max = 0;
    for (i = 0; i < n; i++)
    {
        cin >> p1[i] >> p2[i];
        r_max = (r_max >= p2[i] ? r_max : p2[i]);
    }
    int j = 0;
    for (i = 0; i < n; i++)
    {
        for (j = p1[i]; j <p2[i]; j++)
        {
            pc[j]++;
        }
        for (j = p1[i] + 1; j < p2[i]; j++)
        {
            pd[j]++;
        }
    }
    int max = 0;
    for (i = 0; i < r_max; i++)
    {
        max = (max >= pc[i] ? max : pc[i]);
    }
    for (i = 0; i < r_max; i++)
    {
        if ((pc[i] == max&&i==0)||(pc[i]==max&&pd[i]!=max&&i>0))
        {
            cout << i <<' ';
        }
        if (pc[i] == max && pd[i + 1] != max)
        {
            cout << i + 1 << endl;
        }
    }
}
发表于 2019-08-19 21:53:43 回复(1)
#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);
        }
    }
}

发表于 2019-11-27 01:43:17 回复(0)
80%但是超时了,哎
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)



发表于 2019-11-18 14:03:31 回复(0)
#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;
}

发表于 2019-07-24 10:14:19 回复(1)
1
发表于 2019-05-30 10:38:37 回复(0)