为了拯救因入学人数骤降,面临废弃的学校,牛牛决定成为偶像啦。当然,作为一个偶像,肯定是要上台表演的。
已知牛牛拿到了n个上台表演的机会,第i次表演的上台时间为ti时刻,需要表演mi这么长的时间。
牛牛为了提高自己的知名度,肯定要取得最多的上场次数。请问,牛牛最多能上场多少次呢?
第一行输入一个数字n(1≤n≤100000),表示牛牛获得的上台表演的机会
接下来n行,每行输入两个数字ti(1≤ti≤108)和mi(1≤mi≤108), 表示第i次表演机会的上台时间和该次表演需要的总时间(表演途中不能中断表演退出)。
牛牛最多能上场的次数。
3 1 2 3 2 5 2
3
#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;
}
}
应该使用贪心算法, 把所有表演按照结束时间排序, 结束时间早的在前。
每次选择结束时间最早的表演, 直到没有可选择的(即上一个表演的结束时间晚于所有表演的开始时间)。
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);
}
}
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); }
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% 二维数组排序的方法?
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)
//求大牛帮我看一下 ,我这个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); } }
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; } } }
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); } }
return value;}
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))
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();
}
}