贪心专题

1.活动安排

有若干个活动，第i个开始时间和结束时间是[Si,fi)，只有一个教室，活动之间不能交叠，求最多安排多少个活动？

Input

1
2
3

第一行一个正整数n (n <= 10000)代表活动的个数。
第二行到第(n + 1)行包含n个开始时间和结束时间。
开始时间严格小于结束时间，并且时间都是非负整数，小于1000000000

Output

1	一行包含一个整数表示活动个数。

Input示例

Output示例

博主提供:

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;

struct node{		
	int s,e;		//start , end 
} a[maxn];

//由于使用结构体,所以需要自定义cmp函数
bool  cmp(node x,node y){	
	if(x.e<y.e) return true;
	else if(x.e==y.e&&x.s>y.s) return true;
	return false;
}

int main(){
	int n,i,j,ans,end;
	cin>>n;
	for(i = 0;i<n;i++)
		cin>>a[i].s>>a[i].e;
	sort(a,a+n,cmp);
	ans = 0;
	end = -1e9-100;
	for(i =0;i<n;i++){
		if(a[i].s>=end){	// 结束最早的
			ans++;
			end=a[i].e;
		}
	}
	cout<<ans<<endl;
	return 0;
}

不使用结构体,使用map:

#include <bits/stdc++.h>
#include <cstdio>
using  namespace std;
const int maxn = 1e4 +5;
int main(){
    int N;
    while(scanf("%d",&N) == 1){
        pair<int,int> itv[maxn];
        for(int i = 0 ; i<N; i++) scanf("%d%d",&itv[i].second , &itv[i].first);
        sort( itv , itv + N);
        int ans = 0 ;
        int t = 0;
        for( int i =0 ; i< N ; i++){
            if ( t < itv[i].second ){
                ans ++;
                t = itv[i].first;
            }
        }
        printf("%d",ans);
    }
    return 0;
}

HUD OJ 2037今年暑假不AC

感觉像是板子题，都是时间规划类，需要最多目标的题目。但是在第15行时，必须写<=,否则WA.

<= 的结果是 5 ; < 的结果是 3

经过与上题的对比发现，主要的区别在于这句话：上题规定 开始时间严格小于结束时间，并且时间都是非负整数，小于1000000000 ，而这题 开始时间是可以等于结束时间的

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e4+ 5;
pair<int,int> node[maxn];
int main(){
    int N;
    while( cin >> N){
        if ( !N ) break;
        for(int i=0;i<N;i++) cin >> node[i].second >> node[i].first ;
        sort(node,node+N);
        int ans =0 , endt =0 ;
        for( int i=0 ;i<N;i ++){
            if( endt <= node[i].second ){
                ans ++ ;
                endt = node[i].first;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

字典序比较

include <bits/stdc++.h>

using namespace std;

const int maxn = 1e4 + 5;
char s[maxn];

void solve(int n){
    int a = 0 , b = n-1;
    while( a <= b){
        bool left = false;
        for(int i = 0 ; a+i <=b ; i++){
            if( s[a+i] < s[b-i] ){
                left = true;
                break;
            }else if (s[a+i] > s[b-i]){
                left = false;
                break;
            }else continue;
        }
        if( left ) putchar(s[a++]);
        else putchar(s[b--]);
    }
    putchar('\n');
}

int main(){
    int N;
    scanf("%d",&N);
    scanf("%s",s);
    solve(N);
    return 0;
}