很簡單的題，然而我沒想到，在NOIP上怎么辦嘛QAQ
話說這題不知道怎么分類啊……先扔到玄學里邊把……
原題：
Fj在圣誕節來臨之際，決定給他的奶牛發一些小紅花。
現在Fj一共有N頭奶牛，這N頭牛按照編號1..N，排成一隊，來接受Fj頒發的小紅花，每頭奶牛最多只能戴一朵小紅花，當然，不可能每頭牛都能帶上小紅花。
于是，奶牛們就開始提要求：在編號為第s頭的奶牛到編號為第e頭的奶牛之間，最少要分配X朵小紅花，這些要求Fj當然必須要滿足，現在Fj想知道，在滿足要求的情況下，最少要購買多少朵小紅花。
n≤30000，M≤5000。
?
搞區間，先按照右端點優先遞增排序，用一個flag表示這個位置上有沒有小紅花，枚舉區間，記錄一下這個區間要的小紅花個數，遍歷這個區間，如果區間中這個位置有小紅花了，個數--，然后再從區間右往左，如果這個位置沒有小紅花，個數--并給這個位置添上小紅花，直到個數為0
為什么吶
因為我們是按照右端點優先遞增排序的，所以從右邊往左添加小紅花就能盡可能的保證這些小紅花能覆蓋到更多的區間
一開始要減去小紅花的個數是防止左邊有一些位置有小紅花了，但是我們從右邊遍歷可能遍歷不到
這題很簡單，然而我沒有想出來，我好弱啊QAQ
代碼：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 int n,m; 8 struct cdd{int qleft,qright,qge;}qv[5100]; 9 bool compare(cdd x,cdd y){ return (x.qright==y.qright) ? (x.qleft<y.qleft) : (x.qright<y.qright);} 10 int ans=0; 11 bool flag[310000]; 12 int main(){//freopen("ddd.in","r",stdin); 13 memset(flag,0,sizeof(flag)); 14 cin>>n>>m; 15 for(int i=1;i<=m;i++) scanf("%d%d%d",&qv[i].qleft,&qv[i].qright,&qv[i].qge); 16 sort(qv+1,qv+m+1,compare); 17 for(int i=1;i<=m;i++){ 18 int _ge=qv[i].qge,temp=qv[i].qright; 19 for(int j=qv[i].qleft;j<=qv[i].qright;j++)if(flag[j]) _ge--; 20 for(;_ge>0;temp--)if(!flag[temp]){ flag[temp]=true; ans++; _ge--;} 21 } 22 cout<<ans<<endl; 23 return 0; 24 }
?
