**极致的速度**【题解】

初代

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> x(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }
    
    // 计算前缀和
    vector<long long> s(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        s[i] = s[i - 1] + x[i - 1];
    }
    
    // 存储前缀和对应的索引（因x为正数，s严格递增，每个值唯一）
    unordered_map<long long, int> pos;
    for (int i = 0; i <= n; ++i) {
        pos[s[i]] = i;
    }
    
    long long min_mid = s[n]; // 初始值为全部资产（左右都为0的情况）
    
    // 遍历所有可能的左切割点
    for (int i = 0; i < n; ++i) {
        long long sum_left = s[i + 1];
        long long target = s[n] - sum_left; // 右侧需要达到的总和对应的前缀和
        
        if (pos.count(target)) {
            int j = pos[target];
            if (j > i) { // 确保右侧切割点在左侧切割点右边
                long long current_mid = s[j] - s[i + 1];
                if (current_mid < min_mid) {
                    min_mid = current_mid;
                }
            }
        }
    }
    
    cout << min_mid << endl;
    return 0;
}
    

二代

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> x(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }
    
    // 计算总价值
    long long total = 0;
    for (int val : x) total += val;
    
    long long min_mid = total;  // 初始值为全部资产
    long long left_sum = 0, right_sum = 0;
    int right = n - 1;  // 右侧指针
    
    // 左指针从0开始移动，计算左侧总和
    for (int left = -1; left < n - 1; ++left) {
        if (left >= 0) {
            left_sum += x[left];
        }
        
        // 调整右指针，使右侧总和不小于左侧总和
        while (right > left + 1 && right_sum < left_sum) {
            right_sum += x[right];
            right--;
        }
        
        // 当两侧总和相等时，计算中间部分并更新最小值
        if (left_sum == right_sum) {
            long long current_mid = total - left_sum - right_sum;
            if (current_mid < min_mid) {
                min_mid = current_mid;
            }
        }
    }
    
    cout << min_mid << endl;
    return 0;
}
    

三代

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> x(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i];
    }
    
    // 计算总价值
    long long total = 0;
    for (int val : x) total += val;
    
    long long min_mid = total;  // 初始值为全部资产
    long long left_sum = 0, right_sum = 0;
    int right = n - 1;  // 右侧指针
    
    // 左指针从0开始移动，计算左侧总和
    for (int left = -1; left < n - 1; ++left) {
        if (left >= 0) {
            left_sum += x[left];
        }
        
        // 调整右指针，使右侧总和不小于左侧总和
        while (right > left + 1 && right_sum < left_sum) {
            right_sum += x[right];
            right--;
        }
        
        // 当两侧总和相等时，计算中间部分并更新最小值
        if (left_sum == right_sum) {
            long long current_mid = total - left_sum - right_sum;
            if (current_mid < min_mid) {
                min_mid = current_mid;
            }
        }
    }
    
    cout << min_mid << endl;
    return 0;
}
    

四代

#include <cstdio>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    int x[100000];  // 固定数组比vector更快
    for (int i = 0; i < n; ++i) {
        scanf("%d", &x[i]);
    }
    
    long long total = 0;
    for (int i = 0; i < n; ++i) total += x[i];
    
    long long min_mid = total;
    long long left_sum = 0, right_sum = 0;
    int right = n - 1;
    
    // 合并判断条件，减少循环内分支
    for (int left = -1; left < n - 1; ) {
        if (left >= 0) left_sum += x[left];
        
        // 右指针移动逻辑优化，合并循环条件
        while (right > left + 1 && right_sum < left_sum) {
            right_sum += x[right--];
        }
        
        // 总和相等时更新最小值，减少变量计算
        if (left_sum == right_sum && (total - 2 * left_sum) < min_mid) {
            min_mid = total - 2 * left_sum;
        }
        
        left++;  // 循环变量后移，减少for循环判断
    }
    
    printf("%lld\n", min_mid);
    return 0;
}
    

五代

#include <cstdio>
using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    int x[100000];
    for (int i = 0; i < n; ++i) {
        scanf("%d", &x[i]);
    }
    
    long long total = 0;
    for (int i = 0; i < n; ++i) total += x[i];
    
    long long min_mid = total;
    long long left_sum = 0, right_sum = 0;
    int left = -1, right = n - 1;
    
    // 单循环实现，无嵌套结构
    while (left < n - 1) {
        // 移动左指针并更新左侧总和
        left++;
        if (left > 0) {
            left_sum += x[left - 1];
        }
        
        // 当需要且可能时移动右指针
        if (right > left && right_sum < left_sum) {
            right_sum += x[right];
            right--;
        }
        
        // 检查是否需要继续移动右指针（替代原while循环）
        while (right > left && right_sum < left_sum) {
            right_sum += x[right];
            right--;
        }
        
        // 更新最小值
        if (left_sum == right_sum) {
            long long current_mid = total - 2 * left_sum;
            if (current_mid < min_mid) {
                min_mid = current_mid;
            }
        }
    }
    
    printf("%lld\n", min_mid);
    return 0;
}
    

六代

#include <cstdio>
using namespace std;

int main() {
    int n, i;
    scanf("%d", &n);
    int x[100000];
    for (i = 0; i < n; ++i) scanf("%d", x + i);
    
    long long total = 0;
    for (i = 0; i < n; total += x[i++]);
    
    long long min_mid = total, left_sum = 0, right_sum = 0;
    int left = -1, right = n - 1;
    
    // 单循环无嵌套，指针移动逻辑合并
    while (left < n - 1) {
        // 左指针移动及累加（合并操作）
        if (++left > 0) left_sum += x[left - 1];
        
        // 右指针按需移动（使用for循环替代while，减少分支）
        for (; right > left && right_sum < left_sum; right--)
            right_sum += x[right];
        
        // 总和相等时直接计算并更新最小值（合并判断）
        if (left_sum == right_sum && (total - (left_sum << 1)) < min_mid)
            min_mid = total - (left_sum << 1);
    }
    
    printf("%lld\n", min_mid);
    return 0;
}

七代

#include <cstdio>
using namespace std;
int main() {
    int n,i,x[100000];
    scanf("%d",&n);
    for(i=0;i<n;++i)scanf("%d",x+i);
    
    long long total=0;
    for(i=0;i<n;total+=x[i++]);
    
    long long m=total,l=0,r=0;
    int L=-1,R=n-1;

    while(L<n-1) {
        if(++L>0)l+=x[L-1];
        for(;R>L && r<l;--R)r+=x[R];
        if(l==r && (total-(l<<1))<m)m=total-(l<<1);
    }

    printf("%lld\n",m);
    return 0;
}

极致

#include <cstdio>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
using namespace std;

int x[100000]; // 全局数组放在数据段，避免栈分配开销

int main() {
    int n,i;
    __builtin_ia32_mfence(); // 内存屏障确保数据可见性
    scanf("%d",&n);
    for(i=0;i<n;++i) scanf("%d",x+i);
    
    long long t=0;
    for(i=0;i<n;t+=x[i++]); // 连续累加，充分利用流水线
    
    long long m=t,l=0,r=0;
    int L=-1,R=n-1;
    
    // 展开部分循环，减少循环控制开销
    while(L < n-4) {
        // 一次处理4步左指针移动
        if(++L>0) l += x[L-1];
        for(;R>L && r<l;--R) r += x[R];
        if(l==r && (t-(l<<1))<m) m = t-(l<<1);
        
        if(++L>0) l += x[L-1];
        for(;R>L && r<l;--R) r += x[R];
        if(l==r && (t-(l<<1))<m) m = t-(l<<1);
        
        if(++L>0) l += x[L-1];
        for(;R>L && r<l;--R) r += x[R];
        if(l==r && (t-(l<<1))<m) m = t-(l<<1);
        
        if(++L>0) l += x[L-1];
        for(;R>L && r<l;--R) r += x[R];
        if(l==r && (t-(l<<1))<m) m = t-(l<<1);
    }
    
    // 处理剩余的循环
    while(L < n-1) {
        if(++L>0) l += x[L-1];
        for(;R>L && r<l;--R) r += x[R];
        if(l==r && (t-(l<<1))<m) m = t-(l<<1);
    }
    
    printf("%lld\n",m);
    return 0;
}
    

printf(作者真的做了很长时间，可以点个赞吗，求求了！);