首页 > 试题广场 >

获得最多的奖金

[编程题]获得最多的奖金
  • 热度指数:27497 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
小明在越南旅游,参加了当地的娱乐活动。小明运气很好,拿到了大奖, 到了最后的拿奖金环节。小明发现桌子上放着一列红包,每个红包上写着奖金数额。
现在主持人给要求小明在这一列红包之间“切”2刀,将这一列红包“切”成3组,并且第一组的奖金之和等于最后一组奖金和(允许任意一组的红包集合是空)。最终第一组红包的奖金之和就是小明能拿到的总奖金。小明想知道最多能拿到的奖金是多少,你能帮他算算吗。

举例解释:桌子上放了红包  1, 2, 3, 4, 7, 10。小明在“4,7”之间、“7,10” 之间各切一刀,将红包分成3组 [1, 2, 3, 4]   [7]   [10],其中第一组奖金之和=第三组奖金之和=10,所以小明可以拿到10越南盾。

数据范围:红包数量满足 ,红包金额满足

输入描述:
第一行包含一个正整数n,表示有多少个红包。

第二行包含n个正整数d[i],表示每个红包包含的奖金数额。


输出描述:
小明可以拿到的总奖金
示例1

输入

5
1 3 1 1 4

输出

5

说明

[1,3,1]  [ ]   [1,4] ,其中第一组奖金和是5,等于第三组奖金和。所以小明可以拿到5越南盾 
示例2

输入

5
1 3 2 1 4

输出

4

说明

[1,3]   [2,1]  [4],小明可以拿到4越南盾 
示例3

输入

3
4 1 2

输出

0

说明

[ ]  [4, 1, 2] [ ] ,小明没办法,为了保证第一组第三组相等,只能都分成空的。所以小明只能拿到0越南盾。 

图片说明
图片说明

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {

    /**
     * 双指针思想:
     * 左右指针遍历数组找左边数组的和和右边数组的和比较来移动指针
     * 1.相等则保存当前值,左指针右移,右指针左移动
     * 2.左边和 > 右边和  右指针左移
     * 3.左边和 < 右边和  左指针右移
     */
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        String[] line2 = bf.readLine().split(" ");
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(line2[i]);
        }
        int left = 0, right = n - 1;
        long left_sum = nums[left], right_sum = nums[right], max_sum = 0;
        while (left < right) {
            if (left_sum == right_sum){
                max_sum = left_sum;
                left_sum += nums[++left];
                right_sum += nums[--right];
            }else if (left_sum > right_sum){
                right_sum += nums[--right];
            }else {
                left_sum += nums[++left];
            }
        }
        System.out.println(max_sum);
    }
}
发表于 2019-08-03 13:34:16 回复(8)
import sys
n=int(sys.stdin.readline().strip())
arr=list(map(int,sys.stdin.readline().split()))
left,right=0,n-1
lsum,rsum=arr[0],arr[-1]
res=0
while left<right:
    if lsum<rsum:
        left+=1
        lsum+=arr[left]
    if lsum>rsum:
        right-=1
        rsum+=arr[right]
    if lsum==rsum:
        res=lsum
        left+=1
        right-=1
        lsum+=arr[left]
        rsum+=arr[right]
print(res)

发表于 2019-08-19 16:00:57 回复(2)
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int number;
    cin>>number;
    vector<int> vect;
    while(number--)
    {
        int temp=0;
        cin>>temp;
        vect.push_back(temp);
    }
        long long sum_right=0;
        long long sum_left=0;
        int left=0;
        int right=vect.size()-1;
        long long result;
        while(left<=right)
        {
            if(sum_right==sum_left&&left!=right)
            {
                sum_left+=vect[left];
                sum_right+=vect[right];
                left++;
                right--;
            }
            else if(sum_left>sum_right)
            {
                sum_right+=vect[right];
                right--;
            }
            else
            {
                sum_left+=vect[left];
                left++;
            }
            if(sum_right==sum_left)
            {
                result=sum_right;
            }
        }
    cout<<result<<endl;
    return 0;
}

发表于 2019-07-03 08:33:27 回复(1)
/*
从左右两端共进。
若当前左端大于右端,右端前进一个。
若当前左端小于右端,左端前进一个。
如当前左端等于右端,左右两端都前进一个。
然后再判断左右两端和是否相等,若相等则更新答案。
左端坐标大于右端坐标时,跳出循环。
O(n)。
细节处理:需要用long类型。
当走到中间只剩一个数时,左右两端相等,不能再同时前进了。
*/
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        long ans = 0;
        int left = 0;
        int right = n - 1;
        long sumLeft = 0;
        long sumRight = 0;
        while (left <= right) {
            if (sumLeft == sumRight && left != right) {
                sumLeft += arr[left];
                sumRight += arr[right];
                left++;
                right--;
            } else if (sumLeft > sumRight) {
                sumRight += arr[right];
                right--;
            } else {
                sumLeft += arr[left];
                left++;
            }
            if (sumLeft == sumRight) {
                ans = sumLeft;
            }
        }
        System.out.println(ans);
    }
}

发表于 2019-06-27 19:48:43 回复(0)
import java.util.*;
public class Main{
    //思路:
    //1.定义左指针跟右指针,分别指向第一个红包和最后一个红包
    //2.左指针指向数据和 > 右指针指向数据和,左指针++;
    //3.左指针指向数据和 < 右指针指向数据和,右指针--;
    //4.左指针指向数据和 = 右指针指向数据和,左指针++,右指针--;
    //约束条件是左指针 < 右指针。
    //需要注意的是所有求和的值都要设为long型,会超过int最大范围。
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//红包个数
        int[] d = new int[n];//每个红包奖金数额
        for(int i = 0; i < n; i++){
            d[i] = sc.nextInt();
        }
        int left = 0;
        long leftSum = d[left];
        int right = n - 1;
        long rightSum = d[right];
        long max = 0;
        while(left < right){
            if(leftSum < rightSum){
                left++;
                leftSum += d[left];
            }
            if(leftSum > rightSum){
                right--;
                rightSum += d[right];
            }
            if(leftSum == rightSum){
                max = leftSum;
                left++;
                right--;
                leftSum += d[left];
                rightSum += d[right];
            }
        }
        System.out.println(max);
    }
}

发表于 2019-10-31 20:00:45 回复(0)
双指针求解,当左右两边的和相等时更新收益
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] strArr = br.readLine().trim().split(" ");
        int[] arr = new int[strArr.length];
        for(int i = 0; i < strArr.length; i++) arr[i] = Integer.parseInt(strArr[i]);
        int left = 0, right = n - 1;
        long leftSum = arr[left], rightSum = arr[right];
        long money = 0;
        while(left < right) {
            if(leftSum < rightSum){
                // 左边和小,右移左指针,增加左边和
                left ++;
                if(left >= right) break;
                leftSum += arr[left];
            }else if(leftSum > rightSum){
                // 左边和大,左移右指针,增加右边和
                right --;
                if(left >= right) break;
                rightSum += arr[right];
            }else{
                // 相等的时候更新收益,然后移动左右两个指针并更新左右的和
                money = Math.max(money, leftSum);
                left ++;
                right --;
                if(left >= right) break;
                leftSum += arr[left];
                rightSum += arr[right];
            }
        }
        System.out.println(money);
    }
}


发表于 2021-02-19 18:29:22 回复(0)
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] d = new int[n];
        for (int i = 0; i < n; i++) {
            d[i] = sc.nextInt();
        }
        if (n == 1) {
            System.out.println(0);
            return;
        }
        int i = 0, j = n-1;
        long sum1 = d[0];
        long sum2 = d[j];
        long res = 0;
        while (i < j) {
            if (sum1 == sum2) {
                res = sum1;
                i++;
                j--;
                if (i < j) {
                    sum1 += d[i];
                    sum2 += d[j]; 
                } 
            } else if (sum1 < sum2) {
                i++;
                if (i < j) sum1 += d[i];
            } else {
                j--;
                if (i < j) sum2 += d[j];
            }

        }
        System.out.println(res);
    }
}

发表于 2020-09-03 19:54:49 回复(0)
a,b = int(input()),list(map(int,input().split()))
p,q,s,t = 0,a - 1,0,0
while p - 1 < q + 1:
    if s < t:
        p,s = p + 1,s + b[p]
    elif s > t:
        q,t = q - 1,t + b[q]
    else:
        p,q,r,s,t = p + 1,q - 1,s,s + b[p],t + b[q]
print(r)

发表于 2020-03-13 15:14:39 回复(0)
双指针的做法
左右各一个index,左大右移,右大左移,相同更新max并同时移动
注意用long存结果
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextLong();
        }
        int left = 0;
        long lsum = arr[left];
        int right = n-1;
        long rsum = arr[right];
        long sum = 0L;
        while (left<right){
            if (lsum==rsum){
                left++;right--;
                sum = lsum;
                lsum+=arr[left];
                rsum+=arr[right];
            }else if (lsum<rsum){
                left++;
                lsum+=arr[left];
            }else {
                right--;
                rsum+=arr[right];
            }
        }
        System.out.println(sum);
    }
}


发表于 2019-10-07 00:02:18 回复(0)
// 这题就是贪心算法
// 算法复杂度O(n),额外的O(n)的空间复杂度
// 第一次输入的时候, 用一个数组把累计金额算出来,并且存入sumArray 这个辅助数组
// 第二次遍历的时候,就可以算出尾部的累计值。
// 然后用个result 记录 head <= tail 这个过程中头部和尾部累加相等的值。
// 其实不需要比大小, 累加正整数肯定是最新的最大。

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

int main(){
    int numCount = 0;
    int head = 0;
    long long sumTail = 0;
    long long result = 0;
    vector<int> array;
    cin >> numCount;
    vector<long long> sumArray(numCount,0);
    int tail = numCount - 1;
    if (numCount < 2){
        cout<< 0 << endl;
        return 0;
    }
    int tmp = 0;
    for (int i = 0; i != numCount; i++) {
        cin >> tmp;
        array.push_back(tmp);
        if (i >= 1) sumArray[i] = sumArray[i-1] + tmp;
        else sumArray[i] = tmp;
    }
    sumTail = array[tail];
    while(head <= tail){
        if (sumArray[head] < sumTail) {
            head ++;
        } else if (sumArray[head] == sumTail) {
            result = sumArray[head];
            head++;
        } else {
            tail --;
            sumTail += array[tail];
        }
    }
    cout<< result << endl;
    return 0;

}


发表于 2019-10-02 21:08:26 回复(0)
双向指针,不过注意结果要用long类型,不然可能存不下。
#include<iostream>

using namespace std;

int main() {
	int eNum = 0;
	scanf("%d\n", &eNum);
	int *data = new int[eNum];
	for (int i = 0; i < eNum; i++) {
		cin >> data[i];
	}
	int p1 = 0, p2 = eNum - 1;
	long lSum = p1, rSum = p2;
	long sum1 = data[p1], sum2 = data[p2];
	while (p1 < p2) {
		if (sum1 < sum2) {
			p1++;
			sum1 += data[p1];
		}
		else if (sum1 > sum2) {
			p2--;
			sum2 += data[p2];
		}
		else {
			lSum = sum1; rSum = sum2;
			p1++; p2--;
			sum1 += data[p1];
			sum2 += data[p2];
		}
	}
	if (lSum == 0) {
		printf("%d", 0);
	}
	else {
		printf("%ld", lSum);
	}
}


发表于 2019-09-27 16:16:08 回复(0)
#include<bits/stdc++.h>
using namespace std;
/*先求出总和的数组,然后求出平均数,从总和数组开始位置逐个和平均数比较,确定i、j位置,
 * left为0~i总和,right为j~n-1总和,用双指针i、j从中间往两边走,循环直到left=right为止*/
int main(){
    long n,arr[200000],sum[200000],left=0,right=0;
    cin>>n>>arr[0];
    sum[0]=arr[0];
    for(long i=1;i<n;i++){
        cin>>arr[i];
        sum[i]=sum[i-1]+arr[i]; //最右边为总和
    }
    long i,j,avg=sum[n-1]/2;
    for(int k=0;k<n;k++)
        if(sum[k]>avg&&k>0){
            j=k;    //j~n-1范围
            i=k-1;  //0~i范围
            break;
        }
    left=sum[i];    //左边总和
    right=sum[n-1]-sum[i];  //右边总和
    while(left!=right&&i>=0&&j<n) {  //直到相等就退出
        if(left>right&&i>=0)
            left-=arr[i--];
        if(right>left&&j<n)
            right-=arr[j++];
    }
    cout<<left;
    return 0;
}

发表于 2019-09-08 16:18:48 回复(0)
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> vec(n);
    for (int i = 0; i < n; i++) {
        cin >> vec[i];
    }
    long long res = 0;
    int i = 0, j = vec.size() - 1;
    long long sum1 = vec[i];
    long long sum2 = vec[j];
    while (i < j) {
        if (sum1 == sum2){
            res = sum1;
            sum1 += vec[++i];
            sum2 += vec[--j];
        }
        else if (sum1 < sum2)
            sum1 += vec[++i];
        else
            sum2 += vec[--j];
    }
    cout << res << endl;
}
发表于 2019-08-31 15:25:17 回复(0)
//双指针,两边同时开始计算总和,哪边比另外一边小就往前走一步,直到两边一样就更新最大值


#include <iostream>
#include<set>
#include<map>
#include<vector>
#include<algorithm>
#include<math.h>
//#include<

using namespace std;

int main()
{
    int num ;
    cin>>num;
    vector<unsigned long long>num_vec(num);
    for(int i = 0;i<num;i++)
    {
        cin>>num_vec[i];
    }

    unsigned long long left = 0,right=num-1,ans_left = 0,ans_right = 0;
    unsigned long long left_sum = num_vec[left];
    unsigned long long right_sum = num_vec[right];
    unsigned long long res = 0;

    while(left<right)
    {
        if(left_sum == right_sum)
        {
            res = left_sum;
            left++;
            right--;
            if(left<right)
            {
                right_sum += num_vec[right];
                left_sum += num_vec[left];
            }
        }else if(left_sum > right_sum){
            right--;
            right_sum += num_vec[right];
        }else{
            left++;
            left_sum += num_vec[left];
        }
    }
    cout<<res<<endl;
    return 0;
}

发表于 2019-08-16 10:35:28 回复(0)
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    long  f2l = 0 , l2f = 0;
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    int l = 0, r = n - 1;
    f2l = nums[l];
    l2f = nums[r];
    long  ans = 0;
    while (l < r){
        if(f2l == l2f && f2l > ans) {
            ans = f2l;
            l ++;
            f2l += nums[l];
        }
        if(f2l < l2f) {
            l ++;
            f2l += nums[l];
        }
        else if (l2f < f2l) {
            r--;
            l2f += nums[r];
        }
    }
    cout << ans;
    return 0;
}

发表于 2019-08-02 01:16:20 回复(0)
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int main(){
    int n;
    while(cin>>n){
        ll d[n], Max=0, left=0, right=0;
        for(int i=0;i<n;i++)
            cin>>d[i];
        for(int l=-1,r=n;l<r;){
            if(left == right){
                Max = max(Max, left);
                l++;
                left += d[l];
                r--;
                right += d[r];
            }else if(left < right){
                l++;
                left += d[l];
            }else{
                r--;
                right += d[r];
            }
        }
        cout<<Max<<endl;
    }

    return 0;
}

发表于 2019-07-10 07:25:20 回复(0)
"""
i从前往后求和,j从后往前求和,
当求和相等更新ans,并继续遍历
更新求和小的一侧,直到i>=j停止
ans即为所求
"""
import sys

if __name__ == "__main__":
    # sys.stdin = open('input.txt', 'r')
    n = int(input().strip())
    d = list(map(int, input().strip().split()))
    ans = 0
    i, j, sum_i, sum_j = -1, n, 0, 0
    while i < j:
        if sum_i == sum_j:
            ans = sum_i
            i += 1
            j -= 1
            sum_i += d[i]
            sum_j += d[j]
        elif sum_i > sum_j:
            j -= 1
            sum_j += d[j]
        else:
            i += 1
            sum_i += d[i]
    print(ans)

发表于 2019-07-03 20:33:07 回复(1)

双指针算法

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 2e5 + 10;
int n;
int d[N];

int main() {
    cin >> n;
    for(int i = 0; i < n; i++) scanf("%d", &d[i]);
    LL res = 0;
    LL sum1 = 0;
    LL sum2 = 0;
    for(int i = 0, j = n - 1; i < j;) {
        sum1 += d[i];
        sum2 += d[j];
        if(sum1 < sum2) {
            i++;
            sum2 -= d[j];
        }
        else if(sum1 > sum2) {
            j--;
            sum1 -= d[i];
        }
        else {
            res = sum1;
            i++;
            j--;
        }
    }
    cout << res << endl;
    return 0;
}
发表于 2020-03-30 20:45:49 回复(0)
按顺序做这个名企真题,感觉题只要涉及求和、乘法就要用long long,你就跟着你的long long过去吧😥
发表于 2024-02-21 00:27:46 回复(0)
while True:
    try:
        n = int(input())
        lis = list(map(int,input().split(' ')))
        Money_gain = 0

        right = n-1
        left = 0

        sum1 = lis[left]
        sum2 = lis[right]

        while left < right:
            if sum1 == sum2:
                Money_gain = max(Money_gain,sum1)
                left += 1
                right -= 1
                sum1 += lis[left]
                sum2 += lis[right]
            elif sum1 > sum2 :
                right -= 1
                sum2 += lis[right]
            else:
                left += 1
                sum1 += lis[left] 
        print(Money_gain)     
    except:
        break
        
发表于 2023-06-12 00:21:00 回复(0)