走著。

題目描述

題意簡單到令人發(fā)指！
序列A由N個整數(shù)組成，從中選出一個連續(xù)的子序列，使得這個子序列的和為正數(shù)，且和為所有和大于零的子序列中的最小值.
將這個值輸出，若無解，輸出no solution。

輸入

第一行輸入一個正整數(shù)N (2 < N < 50000)
第二行輸入N個整數(shù)

輸出

輸出最小的正子段和

樣例輸入

3
-1 2 3

樣例輸出

1

思路

• 連續(xù)的子序列的和可以用sum[a] - sum[b]表示
• 符合題目的條件需要滿足兩個條件
  
• a > b
• sum[a] - sum[b] 盡可能的小
• 綜上對sum[] 排序，滿足1,2的就是答案

AC

#include<bits/stdc++.h> #define ll long long #define mem(a, b) memset(a, b, sizeof(a)) #define N 50005 #define P pair<ll, int> using namespace std; P sum[N]; int main() { // freopen("in.txt", "r", stdin);int n;while (~scanf("%d", &n)) {mem(sum, 0);//構(gòu)建pair for (int i = 1; i <= n; i++) {scanf("%lld", &sum[i].first);sum[i].first = sum[i - 1].first + sum[i].first;sum[i].second = i;}//對pair排序 sort(sum + 1, sum + 1 + n); ll ans = 1e9;if (sum[1].first > 0) ans = sum[1].first;//排序之后保證后大于前，只要滿足順序關(guān)系就可以更新 for (int i = 2; i <= n; i++) {//1 到 N的序列單獨判斷 if (sum[i].first > 0) ans = min(ans, sum[i].first);// else continue;if (sum[i].second > sum[i - 1].second && sum[i].first != sum[i - 1].first)ans = min(ans, sum[i].first - sum[i - 1].first);}if (ans == 1e9) printf("no solution\n");else printf("%d\n", ans); } return 0; }

總結(jié)

以上是生活随笔為你收集整理的2060 : Minsum Plus（贪心）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。