【题意】
n头奶牛l瓶防晒霜,奶牛有个可用防晒霜spf的上界a下界b,防晒霜spf值为p可以给c头奶牛用,求最多多少头奶牛涂上防晒霜
【输入】
第一行n,l
接下来n行表示奶牛的可用防晒霜spf的上界a下界b
接下来m行表示防晒霜的spf值和能给几头奶牛用
【输出】
一个数字,表示最多有多少头奶牛可以涂上防晒霜
贪心或者网络流
网络流用sap勉强过
贪心很快
先对防晒霜的spf值排序,再按spf值从小到大的顺序给牛使用防晒霜即可
program poj3614; var n,l,i,j,k,ans:longint; dl,xl,c,a,b,p:array [0..2501] of longint; yes:array [0..2501] of boolean; procedure swap (var a,b:longint); var i:longint; begin i:=a; a:=b; b:=i; end; procedure qsort (s,e:longint); var i,j,k:longint; begin if s>=e then exit; i:=s; j:=e; k:=b[(s+e) div 2]; while i<=j do begin while b[i]<k do inc(i); while b[j]>k do dec(j); if i>j then break; swap(a[i],a[j]); swap(b[i],b[j]); inc(i); dec(j); end; qsort(s,j); qsort(i,e); end; procedure qsort1 (s,e:longint); var i,j,k:longint; begin if s>=e then exit; i:=s; j:=e; k:=p[(s+e) div 2]; while i<=j do begin while p[i]<k do inc(i); while p[j]>k do dec(j); if i>j then break; swap(p[i],p[j]); swap(c[i],c[j]); inc(i); dec(j); end; qsort1(s,j); qsort1(i,e); end; begin read(n,l); for i:=1 to n do read(a[i],b[i]); for i:=1 to l do read(p[i],c[i]); qsort(1,n); qsort1(1,l); ans:=0; fillchar(yes,sizeof(yes),false); for i:=1 to l do for j:=1 to n do if not yes[j] then if (a[j]<=p[i])and(b[j]>=p[i]) then begin yes[j]:=true; inc(ans); dec(c[i]); if c[i]=0 then break; end; writeln(ans); end.