题意： 现有n个集装箱摆在一排，每个集装箱有自己的位置x[i]以及现在装有的物品的数量a[i]。现在要在一个位置将这些东西售卖出去，于是需要将产品运送到某一个位置，已知从位置u到位置v运送一个物品需要的体力值是2*abs(u-v)；问有体力值消耗不超过T的情况下最多可以售卖多少物品。
做法：首先我们可以知道，因为我们要将所有的物品运送到一个位置，于是运送的这些集装箱的位置一定是一段区间，不会是断开的，为什么呢，你想啊，假设Y代表该集装箱被运了，X代表该集装箱没有被运，M代表终点码头，如果是断开的，例如YYXMYYY，我们将最端点的集装箱不运或者少运几个，取决于X码头的产品数量，无论是哪一种，改为X码头晕倒M码头是不是都比原来的省体力呢。
于是我们已经知道是一段连续的区间了，我们就二分最后售卖的物品的数量，对于每次二分的结果，我们验证的时候就O(n)的跑一遍，以每个结点为左端点，运送mid个物品，体力消耗合不合法即可。需要枚举两遍，分别为左右端点。
具体的一些细节看代码，比如说如何计算体力值什么的。
这里官方题解给的时间复杂度是O(n*log(sum(a[i])))，自我感觉因为每个端点作为左端点的时候我们还要向右跑，具体跑多远取决于数据，估计比这个复杂度高，但是有跳出。
代码如下：
#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> using namespace std; const long long maxn = 500010; long long n; ///n个码头 long long T; ///允许的最大的体力值 long long x[maxn], a[maxn]; ///分别代表每个集装箱的位置与现有的容量 long long sum_num[maxn]; ///记录集装箱容量的前缀和 long long sum_T[maxn]; ///记录前i个集装箱的物品全部运到0号节点需要的体力值 这样记录可以O(1)的算出来区间转移的体力值 可以作为一个窍门 void init() { sum_num[0] = 0; sum_T[0] = 0; } void input() { for(long long i=1; i<=n; i++) { scanf("%lld", &x[i]); } for(long long i=1; i<=n; i++) { scanf("%lld", &a[i]); sum_num[i] = sum_num[i-1]+a[i]; sum_T[i] = sum_T[i-1]+2*a[i]*x[i]; ///将该物品也运到0号点 // printf("%lld..%lld... " , sum_num[i] , sum_T[i]); } } long long LL(long long l , long long r) { return (sum_T[r]-sum_T[l-1])-(sum_num[r]-sum_num[l-1])*x[l]*2; ///先将这个区间内的东西移动到0点 再减去多移动的x[l]的距离 } long long RR(long long l , long long r) { return (sum_num[r]-sum_num[l-1])*x[r]*2-(sum_T[r]-sum_T[l-1]); } bool ok(long long ans) { long long l , r , mid , mid_num; ///这里的l,r,mid不是二分 是枚举左右端点和中点 我们知道一定是把这个区间的货物运送到中点 ///这里的中点指的不是区间位置的中点，指的是货物总量中点所在的位置 mid_num = ans/2+1; ///首先我们来看，左端点一定被全部运送，右端点可以不全部运送 l = r = mid = 1; while( true ) { while(r<=n && (sum_num[r]-sum_num[l-1])<ans) r++; ///找到右端点 右端点不一定全部都运 while(mid<r && (sum_num[mid]-sum_num[l-1])<mid_num) mid++; ///找到货物中点所在的位置 if(r>n || mid>n) break; ///枚举到最后的左端点就跳出 long long tmp = (sum_num[r]-sum_num[l-1])-ans; ///确定右端点集装箱剩余多少个物品 // printf("%lld...%lld..%lld..%lld..%lld...%lld...%lld...++++ " , ans , l , r , mid ,RR(l , mid) , LL(mid , r) , 2*tmp*(x[r]-x[mid])); if((RR(l , mid)+LL(mid , r)-2*tmp*(x[r]-x[mid]))<=T) return true; ///RR代表将位置i,j区间内的物品全部移到j位置需要的体力 ///LL代表将位置i,j区间内的物品全部移到i位置需要的体力 l++; } ///接下来我们看右端点一定被全部运送，左端点不一定的情况，同上 l = r = mid = n; while( true ) { while(l>=1 && (sum_num[r]-sum_num[l-1])<ans) l--; while(mid>l && (sum_num[r]-sum_num[mid-1])<mid_num) mid--; if( l<1 || mid<l) break; long long tmp = (sum_num[r]-sum_num[l-1])-ans; // printf("%lld...%lld..%lld..%lld..%lld...%lld...%lld...---- " , ans , l , r , mid , RR(l , mid) , LL(mid , r) , 2*tmp*(x[mid]-x[l])); if((RR(l , mid)+LL(mid , r)-2*tmp*(x[mid]-x[l]))<=T) return true; r--; } return false; } void solve() { long long l , r , mid , res; l = 1; r = sum_num[n]; ///二分枚举最后卖出的货物的数量 下限是1 上线时全部 while( l<=r ) { mid = (l+r)/2; // printf("%lld.. " , mid); if( ok(mid) ) { // printf("%lld.. " , mid); res = mid; l = mid+1; } else { r = mid-1; } } printf("%lld " , res); } int main() { while( scanf("%lld%lld", &n, &T) != EOF ) { init(); input(); // printf("%lld... " , LL(1 , 2)); solve(); } ///别忘了开long long return 0; }