1）二分 作用：在单调的函数上进行查找。
2）三分 作用：在凸形和凹形函数上找最值。
3）用sort进行结构体排序。
2） 主要是下面的shi函数，其余的都基本不变。
点击打开链接
大意：有n个人，找到一个点汇合。
#include <iostream> #include <string.h> #include <stdio.h> #include <math.h> using namespace std; const double EPS=1e-8; double x[50009],y[50009]; int n; double shi(double t){ double ans = 0; for(int i = 0;i<n;i++){ double h = fabs(t-x[i]); ans+=h*h*h*y[i]; } return ans; } double fen(double l,double r){ while(r-l>EPS){ //精度 double ll=l+(r-l)/3; //一分为三 double rr=r-(r-l)/3; double ans1=shi(ll); double ans2=shi(rr); if(ans1>ans2) l=ll; else r=rr; } return l; } int main(){ int T; scanf("%d",&T); for(int t=1;t<=T;t++){ double low=1000009,high=0; scanf("%d",&n)； for(int i = 0;i<n;i++){ scanf("%lf%lf",&x[i],&y[i]); if(low>x[i]) low=x[i]; if(high<x[i]) high=x[i]; } double tmp=fen(low,high); printf("Case #%d: %.0lf\n",t,shi(tmp)); } return 0; }点击打开链接
大意：车子拐弯。
#include <iostream> #include <string.h> #include <stdio.h> #include <math.h> using namespace std; const double EPS=1e-8; const double PI=acos(-1.0); //求pi double x,y,u,w; double shi(double t){ return u*cos(t)+(w-x*cos(t))/sin(t); //当车子左侧与拐点不分开，车子最右下点不离开下平面时，计算车子最左上方点到左面墙壁的垂直距离。 } double fen(double l,double r){ while(r-l>EPS){ double ll=l+(r-l)/3; double rr=r-(r-l)/3;; double ans1=shi(ll); double ans2=shi(rr); if(ans1<ans2) //求最大值时。 l=ll; else r=rr; } return l; } int main(){ while(~scanf("%lf%lf%lf%lf",&x,&y,&u,&w)){ double low = 0,high =acos(-1.0)/2; double tmp = fen(low,high); if(shi(tmp)<=y) printf("yes\n"); else printf("no\n"); } return 0; } 3） sort函数写一下cmp函数。
大意：电视节目表，最多可以看几个节目。
点击打开链接
#include <stdio.h> #include <algorithm> using namespace std; struct node { int t1; int t2; }a[110]; bool cmp(node x, node y){ if(x.t1 !=y.t1) return x.t1 < y.t1; return x.t2 < y.t2; } int main(){ int n,i,j,k,t; while(~scanf("%d",&n)){ if(n==0) break; for(i=0;i<n;i++) scanf("%d%d",&a[i].t1,&a[i].t2); sort(a,a+n,cmp); int p = a[0].t2; int ans = 1; for(i=1;i<n;i++){ if(a[i].t1>=p){ p = a[i].t2; ans++; } else{ if(a[i].t2<p) p = a[i].t2; } } printf("%d\n",ans); } return 0; }
点击打开链接
大意：勇士打怪，有攻击值，有生命值。勇士不会死亡求最少受多少攻击。
#include <stdio.h> #include <algorithm> using namespace std; struct node { int t1; int t2; double t; }a[25]; bool cmp(node x, node y){ return x.t < y.t; //按攻击值与生命值的比值排序。 } int main(){ int n,i; while(~scanf("%d",&n)){ for(i=0;i<n;i++){ scanf("%d%d",&a[i].t1,&a[i].t2); a[i].t = a[i].t1*1.0/a[i].t2; //比值。 } sort(a,a+n,cmp); int ans = 0,p = 0; for(i = 0;i<n;i++){ ans += (a[i].t1+p)*a[i].t2; //所受攻击总数。 p + =a[i].t1; //附加攻击值。 } printf("%d\n",ans); } return 0; } 4）签到。
点击打开链接
#include<stdio.h> int main(){ int n; int a[109]; scanf("%d",&n); int max=0,p1=0,p2=0; for(int i = 1;i<=n;i++){ scanf("%d",&a[i]); if(max<a[i]){ max=a[i]; p1=i; //找到左面最大值。 } } p2=p1; while(a[p2]==max){ p2++; //找到右面最大值。 } p2--; int g=0; for(int i = p1-1;i>0;i--){ //从最大值左面到第一个数字查找是否保持升序。 if(a[i]>=a[i+1]){ g=1; //如果不能g=1。 } } for(int i = p2+1;i<=n;i++){ //从最大值右面到最后一个数字查找是否降序。 if(a[i]>=a[i-1]){ g=1; } } if(g==0) printf("YES\n"); else printf("NO\n"); }