UVA 1450 Airport (二分)PS：两种思路的改错，想AC就看我！！！

这题，神了，网上好多可爱的代码都是有问题的，大体思路都是对的，写的代码死活都AC不了。这题有两种写法，一种是在模拟的过程中对已有资源进行逐个分配，一种是直接比较全部的多出资源和可用资源......来看我的这个的话还是先看看别的大佬的讲解吧,我主要讲代码咋错的,哈哈. 网上的错都出现在啥时候资源不足上,资源不足一定要满足两个条件之一: 1.每个机场需要飞走的飞机比两个机场总共可以飞走的飞机多; 2.每个机场需要飞走的飞机比本场总共可以飞走的飞机多; 很巧的是,在网上的两种写中,上诉两条件,每的缺的都不一样. 下面上代码: //第一种写法 #include<cstdio> #include<algorithm> using namespace std; int n; int w[5005], e[5005]; bool f(int mid) { mid=mid+1; int a=0,b=0,sum=0,nw=0,ne=0; for (int i=0;i<n;i++){ a+=w[i];b+=e[i]; if (a>mid){ // if (a-mid>nw)return false;是错的没考虑条件1; if (a-mid>nw||a-mid>sum)return false; nw-=a-mid; sum-=a-mid; a=mid; } if (b>mid){ // if (b-mid>ne)return false;是错的没考虑条件1; if (b-mid>ne||b-mid>sum)return false; ne-=b-mid; sum-=b-mid; b=mid; } if (nw<a)nw++; if (ne<b)ne++; if (sum<a+b)sum++; } return true; } int main() { int t;scanf("%d", &t); while (t--) { scanf("%d", &n); int sum1=0,sum2=0; for (int i = 0;i < n;i++) { scanf("%d%d", &w[i], &e[i]); sum1+=w[i];sum2+=e[i]; } int l = 0, r = max(sum1,sum2); while (l < r) { int mid = l+(r-l) / 2; if (f(mid))r = mid; else l = mid+1; } printf("%d\n", l); } return 0; } //第二种写法 #include<cstdio> #include<algorithm> using namespace std; int n; int w[5005], e[5005]; bool f(int mid) { mid=mid+1; int a = 0, b = 0, p = 0,pa=0,pb=0; int x, y; for (int i = 0;i < n;i++) { a += w[i];b += e[i]; x = max(a - mid, 0); y = max(b - mid, 0); //if (x + y > p)return false;是错的没考虑条件2; if (x + y > p||x>pa||y>pb)return false; if (a == 0 && b > 0)b--; else if (a > 0 && b == 0)a--; else if (a > 0 && b > 0 ){ if (a + b > p)p++; if (a>pa)pa++;//统计w上可以飞走的飞机个数 if (b>pb)pb++;//统计e上可以飞走的飞机个数 } } return true; } int main() { int t;scanf("%d", &t); while (t--) { scanf("%d", &n); int sum1=0,sum2=0; for (int i = 0;i < n;i++) { scanf("%d%d", &w[i], &e[i]); sum1+=w[i];sum2+=e[i]; } int l = 0, r = max(sum1,sum2); while (l < r) { int mid = l+(r-l) / 2; if (f(mid))r = mid; else l = mid+1; } printf("%d\n", l); } return 0; }