区間問題貪欲戦略個人分析

区間問題よくある問題型:セグメントオーバーライドなどの常用戦略:貪欲にこのような問題に遭遇した場合、3つの状況を考慮する

交差(戦略関連)結合テーマ分析

------
   -------  

相離す(常に考慮しない)

----   ----

は、どの

を先に処理するかを考慮する(順序依存)を含む.

   ---   
---------

例題luogu P 2887【USACO 07 NOV】日焼け止めSunscreen問題面:C個の乳牛が日光浴をしています.それぞれの乳牛が耐えられる日差しの強さには最小値と最大値があります.乳牛は日焼け止めクリームを塗ります.日焼け止めの役割は、太陽の光が体に当たる日差しの強さを一定の値に固定することです.乳牛にやけどをさせないように、効果がありません.L種類の日焼け止めクリームを与えます.それぞれの数と一定の日光強度.各乳牛は日焼け止めクリームを1本しか塗っていませんが、最後に日焼けを楽しむことができる乳牛はいくつかありますかと聞きました.
S o l u t i o n Solution Solutionは、乳牛1匹あたりの許容光強度を区間(または線分)と見なすこの問題について、ソート関数は左端点でソートすることができ、右端点でソートする場合は右端点でソートする例1とする.

----      1
  -----   2

この時、1を先に処理すれば、日焼け止めクリームを選ぶときは小さい頃から大統領選挙までしなければならない.逆に大きいから小さいまで、個人の習慣によって選択します.含む

    ---  1
-------  2

選択の多い2は明らかに下に置くべきです
s o so soソート関数は

il bool cmp(node x,node y){	
	return (x.r==y.r&&x.l<y.l)||(x.r<y.r);
}

C o d e Code Code

#include
#include
#include
#define re register
#define il inline
#define ll long long
using namespace std;

inline int read(){
    int s=0,f=0;char c=getchar();
    while(c<'0'||c>'9') f=(c=='-'),c=getchar();
    while(c>='0'&&c<='9') s=(s<<3)+(s<<1)+(c^'0'),c=getchar();
    return f?-s:s;
}

const int N=2505,M=1005;
int n,m,b[M],ans,now;
struct node{
	int l,r;
}a[N];
/*
     
il bool cmp(node x,node y){		//      
	return (x.l==y.l&&x.ry.l);
}*/
il bool cmp(node x,node y){		//     (       !) 
	return (x.r==y.r&&x.l<y.l)||(x.r<y.r);
}

int main(){
	n=read(),m=read();
	for(re int i=1;i<=n;++i) a[i].l=read(),a[i].r=read();
	for(re int i=1,x,y;i<=m;++i) x=read(),y=read(),b[x]+=y; //+=       
	sort(a+1,a+n+1,cmp);
    for(re int i=1;i<=n;++i)
    /*	for(re int j=a[i].r;j>=a[i].l;--j) */
    	for(re int j=a[i].l;j<=a[i].r;++j)
			if(b[j]){ans++,b[j]--;break;}
	printf("%d
",ans);
	return 0;
}

貪欲さの証明がないことを個人的に理解している人は少ないが、ソートの順番が少し水だと言いたいだけだ.