Codeforces Round #223 (Div. 2)--A. Sereja and Dima
3175 단어 codeforces
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Sereja and Dima play a game. The rules of the game are very simple. The players have n cards in a row. Each card contains a number, all numbers on the cards are distinct. The players take turns, Sereja moves first. During his turn a player can take one card: either the leftmost card in a row, or the rightmost one. The game ends when there is no more cards. The player who has the maximum sum of numbers on his cards by the end of the game, wins.
Sereja and Dima are being greedy. Each of them chooses the card with the larger number during his move.
Inna is a friend of Sereja and Dima. She knows which strategy the guys are using, so she wants to determine the final score, given the initial state of the game. Help her.
Input
The first line contains integer n (1 ≤ n ≤ 1000) — the number of cards on the table. The second line contains space-separated numbers on the cards from left to right. The numbers on the cards are distinct integers from 1 to 1000.
Output
On a single line, print two integers. The first number is the number of Sereja's points at the end of the game, the second number is the number of Dima's points at the end of the game.
Sample test(s)
input
4
4 1 2 10
output
12 5
input
7
1 2 3 4 5 6 7
output
16 12
Note
In the first sample Sereja will take cards with numbers 10 and 2, so Sereja's sum is 12. Dima will take cards with numbers 4 and 1, so Dima's sum is 5.
문제풀이 사고방식: 바둑론처럼 보이지만 사실은 욕심이다.매번 가장 왼쪽 또는 가장 오른쪽만 뽑을 수 있기 때문에 두 개의 바늘 i=n-1, j=0을 켜고 두 사람이 번갈아 뽑는다. 매번 a[i]>a[j]가 있으면 i--;그렇지 않으면 j++;i==j까지 끝납니다.
AC 코드:
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define INF 0x7fffffff
int a[1005];
int main()
{
#ifdef sxk
freopen("in.txt","r",stdin);
#endif
int n;
while(scanf("%d",&n)!=EOF)
{
for(int i=0; i<n; i++)
cin>>a[i];
int ans = 0, anss = 0;
int t = 0;
for(int i=n-1, j=0; i>=j; ){ // i,j
if(a[i] > a[j]){
if(t%2) anss += a[i];
else ans += a[i];
i --;
}
else{
if(t%2) anss += a[j];
else ans += a[j];
j ++;
}
t ++;
}
cout<<ans<<" "<<anss<<endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.