Chinaunix首页 | 论坛 | 博客
  • 博客访问: 59141
  • 博文数量: 29
  • 博客积分: 667
  • 博客等级: 上士
  • 技术积分: 300
  • 用 户 组: 普通用户
  • 注册时间: 2010-04-11 15:55
文章分类
文章存档

2012年(2)

2011年(27)

我的朋友
最近访客

分类: C/C++

2011-09-27 16:43:37

(25分) 给定数列a0,a1…an,求和最接近0的连续子序列,如果有多个,输出所有子序列,每个一行。
 
比如数列为-1,3,1,-2,4,1时,和最接近0的连续子序列有2个,和都是1,分别是1,-2和-1,3,1,-2,还有单独的-1和1共三个。
 
输入输出格式均为每行一个数列,数间用空格分隔。
 
有多个子序列时,先输出开始位置更前的。若开始位置相同,输出结束位置更前的。
 
输入示例
 -1 3 1 -2 4 1
1 2 3
 
输出示例
 -1
-1 3 1 -2
1
1 -2
1
1

  1. #include <iostream>
  2. #include <string>
  3. #include <sstream>
  4. #include <vector>
  5. using namespace std;

  6. vector<int> data;
  7. int ans;

  8. char key[1000000];


  9. int main() {
  10.     string x;
  11.     
  12.     while (gets(key)) {
  13.         x = key;
  14.         ans = INT_MAX;
  15.         stringstream sin(x);
  16.         int t;
  17.         data.clear();
  18.         while (sin >> t) {
  19.             data.push_back(t);
  20.         }
  21.         for (int i = 0; i < data.size(); ++i) {
  22.             int sum = 0;
  23.             for (int j = i; j < data.size(); ++j) {
  24.                 sum += data[j];
  25.                 ans = min(ans, abs(sum));
  26.             }
  27.         }

  28.         for (int i = 0; i < data.size(); ++i) {
  29.             int sum = 0;
  30.             for (int j = i; j < data.size(); ++j) {
  31.                 sum += data[j];
  32.                 if (abs(sum) == ans) {
  33.                     for (int k = i; k <= j; ++k) {
  34.                         if (k != i) {
  35.                             printf(" ");
  36.                         }
  37.                         printf("%d", data[k]);
  38.                     }
  39.                     puts("");
  40.                 }
  41.             }
  42.         }
  43.     }

  44. }
阅读(591) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~