#include<bits/stdc++.h>
using namespace std;
int n,s,t,m,ans,b[2501];
struct node
{
    int x,y;
}a[2501];
bool cmp(node a,node b)
{
    return a.y<b.y;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i+=1)cin>>a[i].x>>a[i].y;
    for(int i=1;i<=m;i+=1)
    {
        cin>>s>>t;
        b[s]+=t;
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i+=1)for(int j=a[i].x;j<=a[i].y;j+=1)if(b[j])
    {
        b[j]-=1;
        ans+=1;
        break;
    }
    cout<<ans;
}

#include <bits/stdc++.h>
struct cow{int l,r;}a[2505];
int yasuo(cow a,cow b){
    return a.r<b.r;}
int main(){
    int c,l,t,s,ans=0,b[2505]={}; std::cin>>c>>l;
    for(int i=0;i<c;i++)std::cin>>a[i].l>>a[i].r;
    for(int i=0;i<l;i++){std::cin>>t>>s;b[t]+=s;}
    std::sort(a,a+c,yasuo);
    for(int i=0;i<c;i++)
        for(int j=a[i].l;j<=a[i].r;j++)
            if(b[j]){b[j]--,ans++; break;}
    std::cout<<ans; return 0;}

题目描述

有C个奶牛去晒太阳 (1 <=C <= 2500)，每个奶牛各自能够忍受的阳光强度有一个最小值minSPF[i]和一个最大值maxSPF[i] (1<=minSPF[i]<=maxSPF[i]<=1000)，太大就晒伤了，太小奶牛没感觉。

而刚开始的阳光的强度非常大，奶牛都承受不住，然后奶牛就得涂抹防晒霜，防晒霜的作用是让阳光照在身上的阳光强度固定为某个值。

那么为了不让奶牛烫伤，又不会没有效果。

给出了L(1 <= L <=2500)种防晒霜。每种的数量cover[i]和固定的阳光强度SPF[i] (1<=SPF[i]<=1000)也给出来了

每个奶牛只能抹一瓶防晒霜，最后问能够享受晒太阳的奶牛有几个。

输入格式

第一行两个整数C和L。

接下来C行，每行两个整数minSPF[i],maxSPF[i]。

再接下来L行，每行两个整数SPF[i]和cover[i]，表示第i种防晒霜的阳光强度和数量。

输出格式

一个整数，表示最多能够享受晒太阳的奶牛数量。

闲话不多说，不太懂这道题的同志们跟我来！跟着我逐步思考，让你秒懂此题！~这题很水的~

STEP 1 审题

经过整理，汇总改编抽象出一下条件：

1.有c条线段，已知它们的端点；

2.有l种点，已知它们的坐标以及每种点的个数；

3.问如果把那些点放入线段中，最多可以放进几个。

看吧，活脱脱的一个贪心中的线段覆盖问题！

STEP 2 规划做题方法

经过审（biao) 题 (qian)，我们了解了这是一道线段覆盖问题，那么，线段覆盖问题怎么做？

方法： 按右端点排序。

理由： 方便处理防晒霜摸到奶牛身上

但是，为什么不按左端点排序呢

证明： 现有三条线段，给出它们的左右端点（按左端点排序后）：

1 6 / / 2 3 / / 3 4

防晒霜两种（只给点的坐标，默认每种一瓶）（按大小排序后）：

3 / / 5

那么按正常的流程，“3”防晒霜给“1 6”线段，则5无法给另外两条线段，ans答案为1.

但如果按右端点排序，则结果为：

2 3 / / 3 4 / / 1 6

那么“3”防晒霜会给“2 3”线段使用，5会给“1 6”，从而有两个结果。

这个反例证明：右端点才能真正确定一条线段的位置

线段（奶牛）按右端点排序后，再从小到大将每个点（防晒霜）排序即可。

题解

30行是不是很短（没有压行哦）

#include<bits/stdc++.h>   //美丽可爱端庄大方的万能头
using namespace std;
int c,l,ans;   //分别记录奶牛数量，防晒霜数量以及结果
struct node{   //结构体储存方便排序
	int a,b;   //两个数据
};
node cow[2501],fss[2501];   //分别储存奶牛信息和防晒霜信息
int cmp(node x,node y){   //排序1：给奶牛按右端点排序
	return x.b<y.b;
}
int cmp1(node x,node y){   //排序2：给防晒霜按左端点排序
	return x.a<y.a;
}
int main(){
	scanf("%d%d",&c,&l);
	for (int i=1;i<=c;i++) scanf("%d%d",&cow[i].a,&cow[i].b);
	for (int i=1;i<=l;i++) scanf("%d%d",&fss[i].a,&fss[i].b);   //正常输入输出
	sort(cow+1,cow+c+1,cmp);   //奶牛排序
	sort(fss+1,fss+l+1,cmp1);   //防晒霜排序
	for (int i=1;i<=c;i++){
		for (int j=1;j<=l;j++){   //循环判断
			if (fss[j].b>0&&fss[j].a>=cow[i].a&&fss[j].a<=cow[i].b){   //判断是否符合点在线段内且该点还有剩余
				fss[j].b--,ans++;   //减去一个相应点，答案+1
				break;   //找到合适点选，就换另一个线段
			}
		}
	}
	printf("%d\n",ans);   //正常输出
	return 0;   //by hetao5487227

按照maxSPF递增的顺序把奶牛排序，依次考虑每头奶牛，对于每头奶牛，找出这头奶牛能用的防晒霜里SPF值最小的使用。 以上的贪心策略是在满足条件的前提下每次选SPF值最小的，这个贪心策略为什么是正确的呢？ 我们考虑这一步策略的作用范围扩展到后续其他奶牛之后产生的影响。

1. 若当前奶牛有可以用的防晒霜，但是不用留给后面的奶牛。这一步必然不优，因为每瓶防晒霜都只能对答案产生1的贡献，留给后面的奶牛还有可能用不上。
2. 若当前奶牛有可用的两瓶防晒霜x和y，且满足SPF[x]<SPF[y],因为我们已经按照maxSPF递增的顺序排序，所以后面的奶牛只能产生“x和y都能用”，“x和y都不能用”，“x不能用，y能用”三种情况，因此让当前奶牛选择SPF值更小的x明显更优。

#include <bits/stdc++.h>
using namespace std;
const int N = 2505;
int n, b[N], s, t, m, ans;
struct node{
	int x, y;
} a[N];
bool cmp(node a, node b){
	return a.y < b.y;
}
int main(){
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
		cin >> a[i].x >> a[i].y;
	for (int i = 1; i <= m; ++i){
		cin >> s >> t;
		b[s] += t;
	}
	sort(a + 1, a + 1 + n, cmp);
	for (int i = 1; i <= n; ++i){
		for (int j = a[i].x; j <= a[i].y; ++j)
			if (b[j]){
				--b[j];
				++ans;
				break;
			}
	}
	cout << ans;
}