下面是对信息学奥赛一本通网站评测上的AC代码的总结
·例一：
题目描述：
设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi。如果选择了活动i，则它在半开时间区间[si, fi)内占用资源。若区间[si, fi)与区间[sj, fj)不相交,则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。选择出由相互兼容的活动组成的最大集合。
代码实现：
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdio> 4 5 using namespace std; 6 7 struct node 8 { 9 int st; 10 int ed; 11 }a[1005]; 12 13 bool cmp(node x,node y) 14 { 15 return x.ed<y.ed; 16 } 17 18 int main() 19 { 20 int n; 21 scanf("%d",&n); 22 for(int i=1;i<=n;++i) scanf("%d%d",&a[i].st,&a[i].ed); 23 sort(a+1,a+n+1,cmp); 24 int t=a[1].ed; 25 int ans=1; 26 for(int i=2;i<=n;++i) 27 { 28 if(a[i].st>=t) 29 { 30 ans++; 31 t=a[i].ed; 32 } 33 } 34 printf("%d",ans); 35 return 0; 36 }
·例二：
题目描述：
现在我们国家开展新农村建设，农村的住房建设纳入了统一规划，统一建设，政府要求每一住户门口种些树。门口路边的地区被分割成块，并被编号成1..N。每个部分为一个单位尺寸大小并最多可种一棵树。每个居民房子门前被指定了三个号码B，E，T。这三个数表示该居民想在B和E之间最少种T棵树。当然，B≤E，居民必须记住在指定区不能种多于区域地块数的树，所以T≤E-B+l。居民们想种树的各自区域可以交叉。你的任务是求出能满足所有要求的最少的树的数量，尽量较少政府的支出。
代码实现：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 5 using namespace std; 6 7 struct line{int s,e,v;}a[5005]; 8 9 int n,m; 10 11 bool used[30005]={0}; 12 13 bool cmp(const line &x,const line &y){return x.e<y.e;} 14 15 void init() 16 { 17 int i; 18 scanf("%d%d",&n,&m); 19 for(i=1;i<=m;++i) scanf("%d%d%d",&a[i].s,&a[i].e,&a[i].v); 20 sort(a+1,a+m+1,cmp); 21 } 22 23 void solve() 24 { 25 int i,j,k,ans=0; 26 for(int i=1;i<=m;++i) 27 { 28 k=0; 29 for(j=a[i].s;j<=a[i].e;++j) if(used[j]) ++k; 30 if(k>=a[i].v) continue; 31 for(j=a[i].e;j>=a[i].s;--j) 32 if(!used[j]) 33 { 34 used[j]=1; 35 k++; 36 ans++; 37 if(a[i].v==k) break; 38 } 39 } 40 printf("%d",ans); 41 } 42 43 int main() 44 { 45 init(); 46 solve(); 47 return 0; 48 }
·例三：
题目描述：
长L米，宽W米的草坪里装有n个浇灌喷头。每个喷头都装在草坪中心线上（离两边各W/2米）。我们知道每个喷头的位置（离草坪中心线左端的距离），以及它能覆盖到的浇灌范围。
请问：如果要同时浇灌整块草坪，最少需要打开多少个喷头？
代码实现：
1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #define N 300005 6 7 using namespace std; 8 9 const double Eps = 1e-5 ; 10 11 inline int wread(){ 12 char c=getchar ();int flag=1,wans=0; 13 while (c<'0'||c>'9'){if (c=='-') flag=-1;c=getchar ();} 14 while (c>='0'&&c<='9'){wans=wans*10+c-'0';c=getchar ();} 15 return wans*=flag; 16 } 17 18 int T; 19 int n,L,W; 20 struct node {double lx,rx;int pos,r;}a[N]; 21 bool e666 (node x,node y){return x.lx<y.lx;} 22 23 int main (){ 24 T=wread(); 25 while (T--){ 26 memset (a,0,sizeof a); 27 n=wread();L=wread();W=wread(); 28 for (int i=1;i<=n;++i){ 29 a[i].pos=wread(),a[i].r=wread(); 30 if (a[i].r*a[i].r-(W*1.0/2.0)*(W*1.0/2.0)<0) a[i].pos=-1,a[i].lx=-1,a[i].rx=-1; 31 //对于不能覆盖完草坪上端的一个圆(例如样例1中的那个夹在草坪中间的圆) 肯定是不会选它的 32 else { 33 a[i].lx=max (0.000000,(double)a[i].pos-sqrt((double)a[i].r*(double)a[i].r-(W*1.0/2.0)*(W*1.0/2.0))); 34 a[i].rx=a[i].pos+sqrt((double)a[i].r*(double)a[i].r-(W*1.0/2.0)*(W*1.0/2.0)); 35 } 36 } 37 38 sort (a+1,a+n+1,e666); 39 40 int nx=1; 41 double s=0;//起点 42 bool F=true;//判断是否能覆盖完整个区间 43 int ans=0;//记录 44 45 while (nx<=n){ 46 ans++; 47 double re=s; 48 while (a[nx].lx<=re && nx<=n){//模板 49 if (a[nx].rx>=re) s=max(s,a[nx].rx); 50 nx++; 51 } 52 if (s>=L) {break;} 53 if (re==s) {F=false;break;}//未更新,请画图____即当前区间与下个区间之间 一定有一段距离,不符合全部覆盖的要求,退出 54 } 55 if (!F) puts("0"); 56 else printf("%d ",ans); 57 } 58 return 0; 59 }
·例四：
题目描述：
某工厂收到了n个产品的订单，这n个产品分别在 A、B 两个车间加工，并且必须先在 A 车间加工后才可以到 B 车间加工。
某个产品i在 A，B 两车间加工的时间分别为Ai，Bi。怎样安排这个产品的加工顺序，才能使总的加工时间最短。
这里所说的加工时间是指：从开始加工第一个产品到最后所有的产品都已在 A，B 两车间加工完毕的时间。
代码实现：
1 #include<cstdio> 2 #include<iostream> 3 4 using namespace std; 5 6 int ans[1005],n,k,i,j,t,a[1005]; 7 int b[1005],m[1005],s[1005]; 8 9 void read() 10 { 11 int i; 12 scanf("%d",&n); 13 for(i=1;i<=n;++i) scanf("%d",&a[i]); 14 for(i=1;i<=n;++i) scanf("%d",&b[i]); 15 } 16 17 void solve() 18 { 19 for(i=1;i<=n;++i){m[i]=min(a[i],b[i]);s[i]=i;} 20 for(i=1;i<=n-1;++i) 21 for(j=i+1;j<=n;++j) 22 if(m[i]>m[j]){swap(m[i],m[j]);swap(s[i],s[j]);} 23 k=0;t=n+1; 24 for(i=1;i<=n;++i) 25 if(m[i]==a[s[i]]){k++;ans[k]=s[i];} 26 else{t--;ans[t]=s[i];} 27 k=0;t=0; 28 for(i=1;i<=n;++i) 29 { 30 k+=a[ans[i]]; 31 if(t<k) t=k; 32 t+=b[ans[i]]; 33 } 34 printf("%d ",t); 35 for(i=1;i<=n;++i) printf("%d ",ans[i]); 36 printf(" "); 37 } 38 39 int main() 40 { 41 read(); 42 solve(); 43 return 0; 44 }