当前位置：首页 > news >正文

【ACWing】110. 防晒（配数学证明）

news 2026/6/30 23:51:54

题目地址：

https://www.acwing.com/problem/content/112/

有C CC头奶牛进行日光浴，第i ii头奶牛需要m i n S P F [ i ] minSPF[i]minSPF[i]到m a x S P F [ i ] maxSPF[i]maxSPF[i]单位强度之间的阳光。每头奶牛在日光浴前必须涂防晒霜，防晒霜有L LL种，涂上第i ii种之后，身体接收到的阳光强度就会稳定为S P F [ i ] SPF[i]SPF[i]，第i ii种防晒霜有c o v e r [ i ] cover[i]cover[i]瓶。求最多可以满足多少头奶牛进行日光浴。

输入格式：
第一行输入整数C CC和L LL。
接下来的C CC行，按次序每行输入一头牛的m i n S P F minSPFminSPF和m a x S P F maxSPFmaxSPF值，即第i ii行输入m i n S P F [ i ] minSPF[i]minSPF[i]和m a x S P F [ i ] maxSPF[i]maxSPF[i]。
再接下来的L LL行，按次序每行输入一种防晒霜的SPF和cover值，即第i ii行输入S P F [ i ] SPF[i]SPF[i]和c o v e r [ i ] cover[i]cover[i]。每行的数据之间用空格隔开。

输出格式：
输出一个整数，代表最多可以满足奶牛日光浴的奶牛数目。

数据范围：
1 ≤ C , L ≤ 2500 1≤C,L≤25001≤C,L≤2500,
1 ≤ m i n S P F ≤ m a x S P F ≤ 1000 1≤minSPF≤maxSPF≤10001≤minSPF≤maxSPF≤1000,
1 ≤ S P F ≤ 1000 1≤SPF≤10001≤SPF≤1000

问题等价于有若干区间，然后有若干点，这些点可能重合，当一个点落在一个区间里，这个点就能匹配一个区间。问这些点最多能匹配多少个区间。

思路是，先将区间按照右端点从小到大排序，然后遍历区间，对于每个区间，找到位置最小的点与之匹配；找不到的话，该区间就略过。

证明：假设上述方案叫A AA，另有某一个最优方案B BB不是这样操作的，我们考虑第一个选点不同的区间，设为I II。如果I II在A AA里被点x xx匹配，但是在B BB里没匹配，因为B BB是最优方案，所以x xx在B BB里肯定匹配了某个区间，我们调整一下，让x xx去匹配I II，这样对于I II而言，两个方案一样了；如果I II在A AA里没匹配，但是在B BB里被x xx匹配，由于A AA是贪心策略，这是不可能的；如果I II在A AA里被x xx匹配，但是在B BB里被y yy匹配，那么y ≥ x y\ge xy≥x，我们在B BB里排序在I II之后的区间里找一个被x xx匹配的区间（如果不存在，那么在B BB里可以直接用x xx而不是y yy去匹配I II），设为J JJ，那么y yy一定能匹配J JJ，调整一下使得x xx匹配I II，y yy匹配J JJ。经过上面的调整，可以将两个方案调整成一样，从而贪心策略就是最优策略。

代码如下：

#include<algorithm>#include<iostream>#include<map>#include<vector>usingnamespacestd;usingPII=pair<int,int>;intc,l;vector<PII>v;map<int,int>mp;intmain(){scanf("%d%d",&c,&l);while(c--){intl,r;scanf("%d%d",&l,&r);v.push_back({l,r});}while(l--){inta,b;scanf("%d%d",&a,&b);mp[a]+=b;}sort(v.begin(),v.end(),[&](auto&p1,auto&p2){returnp1.second<p2.second;});intres=0;for(auto&p:v){intl=p.first,r=p.second;if(autoit=mp.lower_bound(l);it!=mp.end()&&it->first<=r){if(!--it->second)mp.erase(it);res++;}}printf("%d\n",res);}