当前位置: 首页> 教育> 锐评 > 游戏软件开发定制_无锡网站制作平台_互联网营销的五个手段_网站优化查询代码

游戏软件开发定制_无锡网站制作平台_互联网营销的五个手段_网站优化查询代码

时间:2025/7/11 23:16:52来源:https://blog.csdn.net/wuqingshun314159/article/details/146439601 浏览次数:1次
游戏软件开发定制_无锡网站制作平台_互联网营销的五个手段_网站优化查询代码

问题描述

小明是学校里的一名老师,他带的班级共有 n 名同学,第 i 名同学的力量值为 a_i

在闲暇之余,小明决定在班级里组织一场拔河比赛。

为了保证比赛双方实力尽可能接近,需要在这 n 名同学中挑选出两个队伍:

  • 每个队伍内的同学编号连续,分别为:

    {a_l1, a_l1+1, ..., a_r1}
    {a_l2, a_l2+1, ..., a_r2}
    
  • 满足:l1 ≤ r1 < l2 ≤ r2

两个队伍的人数不必相同,但希望这两个队伍中同学们的力量值之和尽可能接近

请计算出力量值之和差距最小的挑选方式。


输入格式

共两行:

  • 第一行为一个正整数 n
  • 第二行为 n 个正整数 a_i,表示每位同学的力量值。

输出格式

输出一行,一个非负整数,表示两个队伍力量值之和的最小差距。


样例输入

5
10 9 8 12 14

样例输出

1

样例说明

一种最优选择方式为:

  • 队伍 1:{a_1, a_2, a_3} = {10, 9, 8},总和为 27
  • 队伍 2:{a_4, a_5} = {12, 14},总和为 26

差值为 |27 - 26| = 1


评测用例规模与约定

  • 对于 20% 的评测用例,n ≤ 50
  • 对于 100% 的评测用例,n ≤ 1000,每个 a_i ≤ 10^9

c++代码

#include<bits/stdc++.h>
#include<stdio.h>using namespace std;typedef long long ll;ll n;
vector<ll> arr, sum_pre;int main() {scanf("%lld", &n);arr = vector<ll>(n + 1, 0);sum_pre = vector<ll>(n + 1, 0);ll ans = LONG_MAX;for (ll i = 1; i <= n; i++) {scanf("%lld", &arr[i]);sum_pre[i] = arr[i] + sum_pre[i - 1];}for (ll i = 1; i <= n; i++) {for (ll j = i; j <= n; j++) {ll k = j + 1, w = j + 1, p1 = sum_pre[j] - sum_pre[i - 1];ll mid;while(w <= n && k <= w) {mid = sum_pre[w] - sum_pre[k - 1];ans = min(ans, abs(p1 - mid));if (mid > p1) k++;if (mid < p1) w++;if (mid == p1) {printf("0");return 0;}}}}printf("%lld", ans);return 0;
}//by wqs

算法思路

不要误以为每个人都要上场,这道题目可以选择让一些人不上场的。

我把他理解为四指针,当然有人说他是双指针也是对的,不同的说法罢了。

i, j两个指针确定第一个队伍的区间,这里只能暴力确定

for (ll i = 1; i <= n; i++) {for (ll j = i; j <= n; j++) {//第一个队伍被确立为[i, j]}
}

w和n两个指针,确立第二个区间,第二个区间不能暴力确立,否则超时

这个问题本质上是在j + 1后面找一个区间使得这个区间的和与某个数最接近,至于这个数就是第一个区间里面的区间和p1。

这样写,时间复杂度为o(n);

ll k = j + 1, w = j + 1, p1 = sum_pre[j] - sum_pre[i - 1];
ll mid;
while(w <= n && k <= w) {mid = sum_pre[w] - sum_pre[k - 1];ans = min(ans, abs(p1 - mid));if (mid > p1) k++;//不考虑w++,因为这样只会让mid越来越比p1大if (mid < p1) w++;//不考虑k++,我们这样只会让mid越来越比p1小if (mid == p1) {printf("0");return 0;}
}
关键字:游戏软件开发定制_无锡网站制作平台_互联网营销的五个手段_网站优化查询代码

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: