2011-06-10 19:38:35Morris
d806. 水火不容
http://zerojudge.tw/ShowProblem?problemid=d806
內容 ：
某天淼淼和焱焱決定要用一個遊戲決一死戰，這個遊戲玩法如下：
一開始有n顆石頭，每顆上面都寫著一個數字，兩個人輪流取石頭，
每人每回合可以取任意數量的石頭，而該人該回合的得分即為其取的石頭中數字的最小值
，你知道他們皆絕頂聰明，因而想要寫個程式事先預測他們的勝負來決定要投奔誰。
輸入說明
：
第一行有一個正整數n(n<=1000000)，代表石頭的數量
第二行有n個正整數，分別代表每顆石頭上面的數字(<=1000000000)
輸出說明
：
一個整數，代表在雙方皆絕頂聰明的情況下，先手最多可以贏後手幾分
範例輸入 ：
3 3 1 1
範例輸出 ：
2
提示
：
出處
：
(管理：shik)
作法描述 by (leopan0922)
假設A為先手的分數
B為後手的分數
我們知道每次都有兩種情況
1種是A拿了而答案不變也就是A-B不變
另一種則是B拿了而答案變成輸入的數+B-A
也就是輸入的數-答案
所以我們只需要由小排到大
找到最大的輸入-目前答案
那就是這題的答案了
作法描述 by (leopan0922)
假設A為先手的分數
B為後手的分數
我們知道每次都有兩種情況
1種是A拿了而答案不變也就是A-B不變
另一種則是B拿了而答案變成輸入的數+B-A
也就是輸入的數-答案
所以我們只需要由小排到大
找到最大的輸入-目前答案
那就是這題的答案了
/**********************************************************************************/
/* Problem: d806 "水火不容" from */
/* Language: C */
/* Result: AC (115ms, 2826KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-02 22:51:48 */
/**********************************************************************************/
#include<stdio.h>
struct Axis{
int t;
}Data[1000000], X[1000000];
void Merge(int l, int m, int h) {
int In1=l, In2=m+1;
int a, b, Top=0;
while(In1<=m && In2<=h)
if((Data[In1].t < Data[In2].t))
X[Top++]=Data[In1++];
else X[Top++]=Data[In2++];
while(In1<=m) X[Top++]=Data[In1++];
while(In2<=h) X[Top++]=Data[In2++];
for(a=0,b=l;a<Top;a++,b++)
Data[b]=X[a];
}
void MergeSort(int l, int h) {
if(l < h) {
int m=(l+h)/2;
MergeSort(l ,m);
MergeSort(m+1,h);
Merge(l,m,h);
}
}
int Input() {
char cha;
unsigned int x = 0;
while(cha = getchar())
if(cha != ' ' && cha != '\n' || cha == EOF) break;
if(cha == EOF) return -1;
x = cha-48;
while(cha = getchar()) {
if(cha == ' ' || cha == '\n') break;
x = x*10 + cha-48;
}
return x;
}
main() {
int N, a;
while(scanf("%d", &N) == 1) {
for(a = 0; a < N; a++) Data[a].t = Input();
MergeSort(0, N-1);
int max = 0;
for(a = 0; a < N; a++)
max = (Data[a].t - max > max) ? Data[a].t - max : max;
printf("%d\n", max);
}
return 0;
}
上一篇：d815. 水火不容II
下一篇：d831. 畢業旅行