上海计算机学会2021年1月月赛C++丙组T1分割队伍

2024-07-10 23:59| 来源: 网络整理| 查看: 265

分割队伍

内存限制: 256 Mb时间限制: 1000 ms

题目描述

有 n 个人在排队办事，其中排在第 i 个位置的人办事时间为 ai。有两个窗口开放，小爱可以将这些人按原始顺序分割成两个队伍，请问，如何分割能够使得两个队列的办事时间总和相差最小？

输入格式第一行，单个整数 n第二行，n 个整数 a1,a2,…,an 输出格式

单个整数：表示两队伍时间总和之差的最小值。

数据范围对于 30% 的数据，1≤n≤100对于 70% 的数据，1≤n≤10000对于 100% 的数据，1≤n≤1000001≤ai≤10000 样例数据

输入: 3 1 1 100 输出: 98 说明: 前两人一个队伍，最后一人单独一个队伍输入: 6 1 2 3 4 5 6 输出: 1 说明: 前四人一个队伍，最后两人一个队伍

解析：本题可以采用双指针的方式分别计算前边队伍和后边队伍的时间和，哪边时间少就给哪边加人，直到两边指针相遇，详见代码：

#include using namespace std; int a[100005]; int n; int main() { cin>>n; for(int i=1;i>a[i]; } int l=1;//前边最后一个人的编号 int r=n;//后边最前一个人的编号 int p=a[1];//前边的和 int q=a[n];//后边的和 while(r-l>1){//只要左右没碰头 if (pa[i]; a[i]+=a[i-1];//计算前缀和 } for(int i=1;i

【本文地址】

公司简介

联系我们