asp.net网站搬迁到移动终端携程网站建设目的
张小明 2026/1/8 19:23:30
asp.net网站搬迁到移动终端,携程网站建设目的,seo网站优化服务商,交易网站建设具体方案题目地址#xff1a;
https://www.acwing.com/problem/content/112/
有CCC头奶牛进行日光浴#xff0c;第iii头奶牛需要minSPF[i]minSPF[i]minSPF[i]到maxSPF[i]maxSPF[i]maxSPF[i]单位强度之间的阳光。每头奶牛在日光浴前必须涂防晒霜#xff0c;防晒霜有LLL种#xff0…题目地址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 IIy yy匹配J JJ。经过上面的调整可以将两个方案调整成一样从而贪心策略就是最优策略。代码如下#includealgorithm#includeiostream#includemap#includevectorusingnamespacestd;usingPIIpairint,int;intc,l;vectorPIIv;mapint,intmp;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(),[](autop1,autop2){returnp1.secondp2.second;});intres0;for(autop:v){intlp.first,rp.second;if(autoitmp.lower_bound(l);it!mp.end()it-firstr){if(!--it-second)mp.erase(it);res;}}printf(%d\n,res);}时间复杂度O ( C log ( C L ) ) O(C\log (CL))O(Clog(CL))空间O ( L ) O(L)O(L)。