【2月13日】杭电OJ刷题总结
TestA：
Max Sum
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 345322 Accepted Submission(s): 82122
Problem Description
Given a sequence a[1],a[2],a[3]…a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.
Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).
Output
For each test case, you should output two lines. The first line is “Case #:”, # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.
Sample Input
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5
Sample Output
Case 1:
14 1 4
Case 2:
7 1 6
Author
Ignatius.L
Recommend
We have carefully selected several similar problems for you: 1176 1087 1069 2084 1058
题解：
#include<iostream>
#include<stdlib.h>
using namespace std;
int main() {
int T;
scanf("%d", &T);
int count;
for(count=1;count<=T;count++) {
int n;
scanf("%d", &n);
int array[1000000];
for (int i = 0; i < n; i++) {
scanf("%d", &array[i]);
}
int sum = 0;
int max = -9999999;
int left = 0, right = 0;
int i;
int end_left = 0;
for (i = 0; i < n; i++) {
sum += array[i];
if (sum > max) {
max = sum;
right = i ;
end_left = left;
}
if (sum < 0) {
sum = 0;
left = i + 1;
}
}
printf("Case %d:\n", count);
printf("%d %d %d\n", max, end_left+1, right+1);
if (count < T) {
printf("\n");
}
}
return 0;
}
错误解法：
为什么一开始会做错？原因未考虑一种情况：1 -1 -2 -3 -4，当sum加1后，left本应该保持在1这个位置不变，可是按照我错误的算法导致了i走到-1 -2 之后，left移到-3那个位置，显然是不对的，正确的做法是，再定义一个变量begin，每判断出一个sum>max，就让左指针left=begin，定死保证这个left不会因后面全负而受变化，begin可以每当sum<0时，都自己变为i+1，但是left总归是最大区间的最左端，如果后面的结果再也判断出来最大值，left就不应该受到变化，而错误的解法恰好使它变化了
Test B
Let the Balloon Rise
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 175451 Accepted Submission(s): 69913
Problem Description
Contest time again! How excited it is to see balloons floating around. But to tell you a secret, the judges’ favorite time is guessing the most popular problem. When the contest is over, they will count the balloons of each color and find the result.
This year, they decide to leave this lovely job to you.
Input
Input contains multiple test cases. Each test case starts with a number N (0 < N <= 1000) – the total number of balloons distributed. The next N lines contain one color each. The color of a balloon is a string of up to 15 lower-case letters.
A test case with N = 0 terminates the input and this test case is not to be processed.
Output
For each case, print the color of balloon for the most popular problem on a single line. It is guaranteed that there is a unique solution for each test case.
Sample Input
5
green
red
blue
red
red
3
pink
orange
pink
0
Sample Output
red
pink
Author
WU, Jiazhi
Source
ZJCPC2004
Recommend
JGShining | We have carefully selected several similar problems for you: 1002 1001 1008 1005 1000
#include<iostream>
#include<cstring>
using namespace std;
int main() {
int N;
while (scanf("%d", &N)) {
if (N == 0) {
break;
}
char balloon[1000+5][1000];
memset(balloon, '\0', sizeof(balloon));
for (int i = 0; i < N; i++) {
scanf("%s", balloon[i]);
}
int max_count = 0;
int max_count_up = 0;
int count = 0;
for (int i = 0; i < N; i++) {
count = 0;
for (int j = 0; j < N&&j!=i; j++) {
if (!strcmp(balloon[i], balloon[j])) {
count++;
if (count > max_count) {
max_count = count;
max_count_up = j;
}
}
}
}
printf("%s\n", balloon[max_count_up]);
}
return 0;
}
投递传音控股等公司7个岗位
