11006: 【原1006】求和游戏

题目

题目描述

author: 梁晨锦 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1006

Description

石柱上有一排石头键盘，每个键上有一个整数。请你在键盘上选择两个键，使这两个键及其之间的键上的数字和最大。如果这个最大的和不为正，则输出“Game Over"。

Input Format

第1行：键的个数n。

第2..n+1行：键上的数字整数 \( a_i \)。

\( -100 \leq a_i \leq 100 \)

对于70%的数据，\( 2 \leq n \leq 1,000 \)

对于100%的数据，\( 2 \leq n \leq 1,000,000 \)

Output Format

一行，最大和或者”Game Over"。

Sample Input

5
3
-5
7
-2
8

Sample Output

13

Sample Input

3
-6
-9
-10

Sample Output

Game Over

Hints

数据得到了增强！

• 感谢 曹宇 <caoyu601 at live.com>
• 感谢 Rozc <i at rozc.farm>

CallMeInk's solution

# include<iostream>
using namespace std;

int main(){
    int a[1000001];
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    int maxh=a[1];
    int max=-1000;
    for(int i=2;i<=n;i++){
        if (maxh<0) {
                        if (maxh+a[i]>max) max=maxh+a[i];
                        maxh=a[i];}
        else {
                maxh += a[i];
                if (maxh>max) max=maxh;
                }
    }
    if (max>0) cout << max;
    else cout << "Game Over" << endl;
    return 0;
}

FineArtz's solution

/* 求和游戏 */
#include <iostream>
using namespace std;

int main(){
    int n, t;
    cin >> n;
    cin >> t;
    int MinSum = t, CurSum = t, ans = t;
    for (int i = 2; i <= n; ++i){
        cin >> t;
        CurSum += t;
        ans = max(ans, CurSum - MinSum);
        MinSum = min(MinSum, CurSum - t);
    }
    if (ans > 0) cout << ans << endl;
    else cout << "Game Over" << endl;
    //cout << ans << endl;
    return 0;
}

ligongzzz's solution

#include "iostream"

using namespace std;

constexpr auto maxnum = 1000009;
constexpr int inf = 10000000;

//求解
template <class T>
T bilibili(T* input, int num) {
    if (num == 1) return -inf;
    else if (num == 2) return input[0] + input[1];
    //分成两块
    int center = num / 2;
    T a = bilibili(input, num / 2), b = bilibili(input + num / 2, num - num / 2);
    //寻找左右的最大值
    T maxl = -inf, maxr = -inf, templ = 0, tempr = 0, count = 0;
    for (int i = num / 2 - 1; i >= 0; i--) {
        templ += input[i];
        maxl = maxl < templ ? templ : maxl;
    }
    for (int i = num / 2; i < num; i++) {
        tempr += input[i];
        maxr = maxr < tempr ? tempr : maxr;
    }
    maxl += maxr;
    T max = a > b ? a : b;
    max = max > maxl ? max : maxl;
    return max;
}
int input[maxnum];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> input[i];
    }
    int ans = bilibili(input, n);
    if (ans > 0) {
        cout << ans << endl;
    }
    else {
        cout << "Game Over" << endl;
    }

    return 0;
}

WashSwang's solution

#include <cstdio>
#include <iostream>
using namespace std;
int last,cur,now=-500,maxn,n;
int main() {
    scanf("%d%d",&n,&last);
    for (int i=1;i<n;++i)
    {
        scanf("%d",&cur);
        now=max(cur+now,cur+last);
        last=cur;
        if (now>maxn) maxn=now;
    }
    if (maxn) cout<<maxn<<endl;
    else cout<<"Game Over"<<endl;
    return 0;
}

yyong119's solution

#include <iostream>
#include <cmath>
int num[1000001],pre[1000001];
int n,i,nmax,j,flag;
int main(){
    using namespace std;
    cin>>n;
    if (n<=100){
        for (i=1; i<=n; i++){
            cin>>num[i];
            num[i]+=num[i-1];
        }
        for (i=1; i<n; i++)
            for (j=i+1; j<=n; j++) nmax=max(num[j]-num[i-1],nmax);
    }else{
        for (i=1; i<=n; i++) cin>>num[i];
        for (i=1; i<=n; i++){
            if (pre[i-1]+num[i]<0) flag=0;
            else{
                pre[i]=pre[i-1]+num[i];
                flag++;
            }
            if ((pre[i]>nmax)&&(flag>=2)) nmax=pre[i];
        }
    }
    if (nmax) cout<<nmax;else cout<<"Game Over";
    return 0;
}