首页 > 试题广场 >

牛牛偶像养成记

[编程题]牛牛偶像养成记

热度指数：682 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

为了拯救因入学人数骤降，面临废弃的学校，牛牛决定成为偶像啦。当然，作为一个偶像，肯定是要上台表演的。

已知牛牛拿到了n个上台表演的机会，第i次表演的上台时间为t_i时刻，需要表演m_i这么长的时间。

牛牛为了提高自己的知名度，肯定要取得最多的上场次数。请问，牛牛最多能上场多少次呢？

输入描述:

第一行输入一个数字n(1≤n≤100000)，表示牛牛获得的上台表演的机会
接下来n行，每行输入两个数字t_i(1≤ti≤10⁸)和m_i(1≤m_i≤10⁸), 表示第i次表演机会的上台时间和该次表演需要的总时间（表演途中不能中断表演退出）。

输出描述:

牛牛最多能上场的次数。

示例1

输入

输出

算法知识视频讲解

蛟龙吐火球丰

#include<iostream>
#include <vector>
#include <algorithm>

using namespace std;
int cnt;
bool com(pair<long,long>&a,pair<long,long>&b)
{
    return a.second<b.second;
}
int main()
{
    int n;
    while(cin>>n)
    {
        vector<pair<long,long>> co(n);
        for(int i=0;i<n;i++)
        {      
            cin>>co[i].first>>co[i].second;
            co[i].second+=co[i].first;
        }
        sort(co.begin(),co.end(),com);
        cnt=0;
        long curtime=0;
        for(int i=0;i<n;i++)
        {
           if(co[i].first>=curtime)
           {
               cnt++;
               curtime=co[i].second;
           }
        }
        cout<<cnt<<endl;
    }
}

发表于 2018-06-30 08:52:40 回复(0)

菜鸟-国内供应链技术内推

应该使用贪心算法，把所有表演按照结束时间排序，结束时间早的在前。
每次选择结束时间最早的表演，直到没有可选择的（即上一个表演的结束时间晚于所有表演的开始时间）。

import java.util.Arrays;
import java.util.Scanner;
import java.util.Comparator;
public class Main {
    public static class Perform {
        int start;
        int duration;
        public Perform(int s, int d) {
            start = s;
            duration = d;
        }
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Perform[] performs = new Perform[N];
        for (int i = 0; i < N; i++) {
            int start = sc.nextInt();
            int duration = sc.nextInt();
            performs[i] = new Perform(start, duration);
        }
        //用了java8 的lambda 表达式，按照表演结束时间排序
        Arrays.sort(performs, Comparator.comparingInt(p -> (p.duration+p.start)));
        int count = 0;
        int lastMoment = 0;
        for (int i = 0; i < N; i++) {
            //每次选择表演时间在上次表演结束后的第一个节目
            if (performs[i].start >= lastMoment) {
                count++;
                lastMoment = performs[i].start + performs[i].duration;
            }
        }
        System.out.println(count);
    }
}

发表于 2018-07-05 16:02:41 回复(0)

w布响丸辣

while(n = readline()){
    var arr = [];
    for(var i=0;i<n;i++){
        var line = readline().split(' ');
        arr.push(line);
        arr[i].start = parseInt(line[0]);
        arr[i].end = arr[i].start + parseInt(line[1]);
    }
    arr.sort(function(a,b){
    	return a.end - b.end;
    });
    var res = 0,t = 0;
    for(var i=0;i<n;i++){
    	if(t<=arr[i].start){
    		res++;
    		t = arr[i].end;
    	}
    }
    print(res);
    
}

编辑于 2018-09-17 21:58:07 回复(0)

想被叫靓仔的废话选手

import java.util.Scanner;
import java.util.Arrays;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] perform = new int[n][2];
for(int i = 0;i<n;i++){
perform[i][0] = sc.nextInt();
perform[i][1] = sc.nextInt();
}
Arrays.sort(perform,(int[] o1,int[] o2)->(o1[0]+o1[1]-o2[0]-o2[1]));
int res = 1;
int startTime = perform[0][0]+perform[0][1];
for(int i = 1;i<n;i++){
if(startTime<=perform[i][0]){
res++;
startTime = perform[i][0]+perform[i][1];
}

}
System.out.println(res);
}
}

发表于 2022-11-16 23:52:59 回复(0)

芨荠

import java.util.*;
public class Main{
    public static class Perfrom{
        int start;
        int duration;
        Perfrom(int start, int duration){
            this.start = start;
            this.duration = duration;
        }
    }

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Perfrom[] perfrom = new Perfrom[n];
        int start,duration;
        int count = 0, lastmoment = 0;
        for(int i=0;i<n;i++){
            start = in.nextInt();
            duration = in.nextInt();
            perfrom[i] = new Perfrom(start, duration);
        }
        sort(perfrom, n);
        for(int i=0;i<n;i++){
            if(perfrom[i].start>=lastmoment){  count++;  lastmoment = perfrom[i].start + perfrom[i].duration;
            }
        }
        in.close();
        System.out.println(count);
    }

    public static void sort(Perfrom[] perfrom, int n){
        Perfrom temp = new Perfrom(0,0);
        for(int i=0;i<n;i++){  for(int j=i+1;j<n;j++) {  //表演结束时间排序，因为有的duration时间很长。   if(perfrom[i].start+perfrom[i].duration>perfrom[j].start+perfrom[j].duration){   temp = perfrom[i];   perfrom[i] = perfrom[j];   perfrom[j] = temp;   }    }
        }
    }
} 您的代码已保存 运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。 case通过率为50.00% 二维数组排序的方法？

编辑于 2018-10-07 14:04:30 回复(0)

为啥要起名字

n=int(input())
times=[]
for i in range(n):
    line=list(map(int,input().strip().split()))
    start,end=line[0],line[0]+line[1]
    times.append([start,end])
times.sort(key=lambda x:x[1])
temp,count=0,0
for i in range(n):
    if times[i][0]>=temp:
        count+=1
        temp=times[i][1]
print(count)

发表于 2018-07-24 15:44:36 回复(0)

求天求地求Offer


	//求大牛帮我看一下 ，我这个dp怎么不对了啊



	importjava.util.*;



	publicclassMain{



	publicstaticvoidmain(String[] args){



	Scanner sc=newScanner(System.in);



	HashMap<Integer,Integer> map=newHashMap<Integer,Integer>();



	map.put(0,0);



	intn=sc.nextInt();



	inttime=0;



	intspend=0;



	intmax=0;



	for(inti=0;i<n;i++){



	time=sc.nextInt();



	spend=sc.nextInt();



	map.put(time,spend);



	max=Math.max(time,max);



	}



	int[]dp=newint[max+1];//表示第i个片段所能有的最多的次数



	for(inti=1;i<=max;i++){



	for(intj=i-1;j>=0;j--){



	if(map.containsKey(j)&&j+map.get(j)<=i){



	dp[i]=dp[j]+1;



	break;



	}



	if(j==0)



	dp[i]=1;



	}



	}



	System.out.println(dp[max]);



	}



	}



	



	//参考了上面大神的思路，改进了代码：



	import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int array[][]=new int[n][2];
        for(int i=0;i<n;i++){
            array[i][0]=sc.nextInt();//时间点
            array[i][1]=sc.nextInt();//时间段
        }
        Arrays.sort(array,new Comparator<int[]>(){//按每段时间的终结点来排序
            @Override
            public int compare(int arr1[],int arr2[]){
                return arr1[0]+arr1[1]-arr2[0]-arr2[1];
            }
        });
        int num=0;
        int lastTimeEnd=0;
        for(int i=0;i<n;i++){//如果直接取 上一个时间段的结束时间也是不对，当出现一个时间段与上下两个有交叉的时候 就会差错
            if(array[i][0]>=lastTimeEnd){//所以取当前点的起始时间大于上一被包含时间段的终止时间就 num++
                num++;
                lastTimeEnd=array[i][0]+array[i][1];
            }
        }
        System.out.println(num);
    }
}

编辑于 2018-07-04 23:23:33 回复(0)

桃符

public class Idor {
    /**
     * 
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Idor idor = new Idor();
        Queue<prog> queue = new LinkedList<>();
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int num = 0;
        queue.add(idor.new prog(0, 0));
        List<prog> lists = new ArrayList<prog>();
        for (int i = 0; i < n; i++) {
            int start = scan.nextInt();
            int process = scan.nextInt();
            lists.add(idor.new prog(start, process));
        }
        Collections.sort(lists);
        for(int i = 0 ;i < n ; i++){
            System.out.println(lists.get(i).getStartTime()+"||"+lists.get(i).getEndTime());
        }
        for(int i = 0;i<n;i++){
            prog tmp = queue.element();
            if(lists.get(i).getStartTime()>=tmp.getEndTime()){
                queue.remove();
                queue.add(lists.get(i));
                num++;
            }
        }
        System.out.println(num);
    }
    
    class prog implements Comparable<prog>{
        private int startTime;
        private int processTime;
        public prog(int t,int p){
            this.startTime = t;
            this.processTime = p;
        }
        public int getStartTime() {
            return startTime;
        }
        public int getProcessTime() {
            return processTime;
        }
        public int getEndTime() {
            return this.startTime+this.processTime;
        }
        @Override
        public int compareTo(prog o) {
            // TODO Auto-generated method stub
            return this.startTime+this.processTime-o.startTime-o.processTime;
        }
    }
}

发表于 2018-07-02 23:23:32 回复(0)

Java

刘禅挥泪斩孔明

import java.util.*;
public class Main implements Comparable<Main> {//See Main as Act
  int startTime, endTime;

  Main(int startTimeInit, int duration) {
    this.startTime = startTimeInit;
    this.endTime = startTimeInit + duration;
  }

  public int compareTo(Main other) {return this.endTime - other.endTime;}

  public static void main(String[] args) {
    PriorityQueue<Main> pq = new PriorityQueue<>();
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt(), cnt = 0, lastEndTime = 0;

    while (n-- != 0)
      pq.add(new Main(sc.nextInt(), sc.nextInt()));
    while (pq.size() != 0) {
      if (pq.peek().startTime >= lastEndTime) {
        cnt++;
        lastEndTime = pq.peek().endTime;
      }
      pq.poll();
    }
    System.out.println(cnt);
  }
}

发表于 2018-06-28 23:49:37 回复(0)

1367356

import java.util.*;

/**
* @program: GradleTestUseSubModule
* @author: Yafei Li
* @create: 2018-06-27 22:51
* 牛牛偶像养成记
**/
public class Main {
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);

int n = scanner.nextInt(); //n

Map<Integer, Integer> map = new HashMap<>();
Set<Integer> set = new TreeSet<>();

for (int i = 0; i < n; i++) {
int i0 = scanner.nextInt();// 开始时间
int i1 = scanner.nextInt(); //占据时间
set.add(i0); //排好序的
map.computeIfPresent(i0,(key,value)->{
if (i1+i0 > value) {

        return value;

}
return i1+i0;
});
map.putIfAbsent(i0, i1+i0);
}

Iterator<Integer> sets = set.iterator();
int startTime=sets.next();
int endTime = map.get(startTime);
int count=1;
while (sets.hasNext()) {
int next = sets.next();
if (next < endTime) {
if (map.get(next) < endTime) {
endTime = map.get(next);
}
}else {
startTime=next;
endTime = map.get(next);
count++;
}
}
System.out.println(count);
}
}

发表于 2018-06-28 15:01:06 回复(0)

午光

n = int(input())
t = []
m = []
for i in range(n):
    ti,mi = map(int, input().split(' '))
    t.append(ti)
    m.append(mi+ti)
period = sorted(zip(m,t))
res = [period[0]]
for x in period:
    if x[1] >= res[-1][0]:
        res.append(x)
print(len(res))

发表于 2018-06-27 22:08:28 回复(0)

hwj666


	n =input()



	times =[]



	res =[]



	for_ inrange(int(n)):



	    tm =input()



	    ti,mi =tm.split()



	    ti,mi =int(ti),int(mi)



	    times.append((ti,ti+mi))



	times =sorted(times,key=lambdax:x[1])



	res.append(times[0])



	fortime intimes[1:]:



	    iftime[0] >=res[-1][1]:



	        res.append(time)



	print(len(res))

发表于 2018-06-27 19:42:20 回复(0)

Samuelyo

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
public class NiuNiuIdol {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int num = sc.nextInt();
            List list = new ArrayList();
            for (int i = 0; i < num; i++) {
                int start = sc.nextInt();
                int end = start + sc.nextInt();
                list.add(new int[] { start, end });
            }
            Collections.sort(list, new Comparator() { public int compare(int[] o1, int[] o2) {
                    if (o1[1] != o2[1]) {
                        return o1[1] - o2[1];
                    } else {
                        return o1[0] - o2[0];
                    }
                }
            });
            int count = 1;
            int start = list.get(0)[0];
            int end = list.get(0)[1];
            for (int i = 1; i < list.size(); i++) {
                int[] cur = list.get(i);
                if (cur[0] >= end) {
                    count++;
                    end = cur[1];
                }
            }
            System.out.println(count);
        }
        sc.close();
    }
}

编辑于 2018-06-23 12:12:14 回复(0)