HDU-1858-Max Partial Value I,有坑点,不难;
2024-09-30 07:50:46
Max Partial Value I
Time Limit: 1000/5000 MS (Java/Others) Memory Limit: 32768/65535 K (Java/Others)
Problem Description
HenryFour has a number of stones which have different values from -4444 to 4444. He puts N stones in a line and wants to find the max partial value of these N stones.
Assume the values of the N stones in line are: v1, v2, v3, v4, ..., vN. The partial vaule of stones from Lth stone to Rth stone (1 ≤ L ≤ R ≤ N) is the sum of all the stones between them. i.e. PartialV(L, R) = v[L] + v[L+1] + .... + v[R] (1 ≤ L ≤ R ≤ N)
Since the number of stones (N) is very very large, it is quite difficult for HenryFour to find the max partial value. So could you develop a programme to find out the answer for him?
Assume the values of the N stones in line are: v1, v2, v3, v4, ..., vN. The partial vaule of stones from Lth stone to Rth stone (1 ≤ L ≤ R ≤ N) is the sum of all the stones between them. i.e. PartialV(L, R) = v[L] + v[L+1] + .... + v[R] (1 ≤ L ≤ R ≤ N)
Since the number of stones (N) is very very large, it is quite difficult for HenryFour to find the max partial value. So could you develop a programme to find out the answer for him?
Input
There are several test cases in the input data. The first line contains a positive integer T (1 ≤ T ≤ 14), specifying the number ot test cases. Then there are T lines. Each of these T lines contains a positive number N followed by N integers which indicate
the values of the N stones in line.
1 ≤ N ≤ 1,000,000
-4444 ≤ v[i] ≤ 4444
the values of the N stones in line.
1 ≤ N ≤ 1,000,000
-4444 ≤ v[i] ≤ 4444
Output
Your program is to write to standard output. For each test case, print one line with three numbers seperated by one blank: P L R. P is the max partial value of the N stones in line. L and R indicate the position of the partial stones. If there are several Ls
and Rs that have the same value PartialV(Li, Ri) = P, please output the minimum pair. For pair (Li, Ri) and (Lj, Rj), we define (Li, Ri) < (Lj, Rj) if and only if: Li < Lj or (Li == Lj and Ri < Rj)
and Rs that have the same value PartialV(Li, Ri) = P, please output the minimum pair. For pair (Li, Ri) and (Lj, Rj), we define (Li, Ri) < (Lj, Rj) if and only if: Li < Lj or (Li == Lj and Ri < Rj)
Sample Input
3
4 32 -39 -30 -28
8 1 2 3 -10 1 -1 5 1
10 14 -12 -8 -13 3 5 42 -24 -32 -12
Sample Output
32 1 1
6 1 3
50 5 7
记得以前做过一样的题,而且还水过了,但在这里WA了一整天,整个人都不好了,如果要求最大和的话分分钟水过,但又要求把下标求出,,,”
If there are several Ls and Rs that have the same value PartialV(Li, Ri) = P, please output the minimum pair. For pair (Li, Ri) and (Lj, Rj), we define (Li, Ri) < (Lj, Rj) if and only if: Li < Lj or (Li == Lj and
Ri < Rj) “,千万要注意这点,是要在最大和相同的前提下把最靠近左边的输出,如 0 1,输出应该是 1 1 2;而不是1 2 2;
解决了这个问题还要注意用long long ,不过目测不会超int啊,奇怪;
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
const int N=1000000+10;
int a[N];
int main()
{
int t,n,i,j,k;
long long maxsum,x;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
x=0;
maxsum=-10000000;
j=k=1;
int j1=1,k1=1;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(x>=0)
{
x+=a[i];
k1=i;
}
else
{
x=a[i];
j1=k1=i;
}
if(x>maxsum)
{
maxsum=x;
j=j1;
k=k1;//核心也就这么一点,连动规都不算;
}
}
printf("%I64d %d %d\n",maxsum,j,k);
}
return 0;
}
最新文章
- ES6 基础知识
- delphi 读写文本
- 在office2010怎么样删除图片背景
- 【CodeVS】 p1696 奇怪的函数
- [CareerCup] 8.7 Chat Server 聊天服务器
- 消息通信库ZeroMQ 4.0.4安装指南
- MooFest_二维树状数组
- vb6中webbrowser控件树转换备忘
- 基于CentOS与VmwareStation10搭建Oracle11G RAC 64集群环境:4.安装Oracle RAC FAQ-4.4.无法图形化安装Grid Infrastructure
- 基于BaseHTTPServer的简单存储服务器
- IDL 实现PCA算法
- C标准I/O建立一个文件仓库
- 2017-2018 ACM-ICPC, Central Europe Regional Contest (CERC 17)
- 关于HTTP协议学习(一)
- jasperreports+IReport 5.56,集成到Spring MVC4.0案例
- ftp服务器使用-windowsftp服务起搭建
- 巧用border效果
- BZOJ1023:[SHOI2008]cactus仙人掌图(圆方树,DP,单调队列)
- TCP可靠传输:校验和,重传控制,序号标识,滑动窗口、确认应答
- 同一个页面引用不同版本jquery库