Решение задачи №648 «Азартный Шрэк» с ACMP





Решение задачи №648 «Азартный Шрэк» с ACMP

Условие задачи

Как-то раз Шрек решил посетить казино. Не будучи заядлым любителем азартных игр, Шрек обнаружил, что он не знает правил ни одной из игр, доступных в казино. Недолго думая, Шрек решил все-таки поиграть. Его взор привлекла игра с довольно незамысловатыми правилами.

На игровом столе лежат N карточек. На каждой карточке написано целое положительное число. Игра проходит между игроком и крупье. Карточки лежат на столе числами вниз. Игра заключается в том, что игрок открывает ровно N/2 карточек. Сумма всех чисел, написанных на карточках открытых игроком, называется “суммой игрока”. Следующим ходом крупье открывает оставшиеся N/2 карточек. Сумма всех чисел, написанных на карточках открытых крупье, называется “суммой крупье”. Выигрыш игрока определяется разностью чисел между “суммой игрока” и “суммой крупье”. Очевидно, что полученная разность может быть отрицательным числом. Это свидетельствует о том, что игрок проиграл и должен казино соответствующую сумму.

Все бы ничего, но Шрек обладает способностью видеть надписи сквозь бумагу любой плотности. Ваша задача определить максимальную сумму выигрыша, которую может получить Шрек с учетом того, что он видит все числа, написанные на карточках.

Входные данные
Первая строка входного файла INPUT.TXT содержит одно четное натуральное число N (2 ≤ N ≤ 100). Вторая строка входного файла содержит ровно N чисел Ai(1 ≤ Ai ≤ 106) – числа, написанные на игральных карточках. Все числа в строке разделяются одиночными пробелами, Ai – число, написанное на i-й карточке. Карточки нумеруются последовательно, начиная с единицы.

Выходные данные
Единственная строка выходного файла OUTPUT.TXT должна содержать ровно одно целое число – максимальный выигрыш, который может получить Шрек с учетом своей уникальной способности видеть числа, написанные на карточках.

#include<iostream>
using namespace std;
void InsertSort(int a[],int n)
{
int i,j,k;
for(i=1;i<n;i++)
{
j=i;k=a[i];
while(j&&k<a[j-1])
{
a[j]=a[j-1];j--;}
a[j]=k;
}
}
int Sum(int a[],int n)
{
int i,s=0;
for(i=0;i<n;i++)s+=a[i];
}
main ()
{
int a[1000],n,i,s1=0,s2=0;
cin>>n;
for(i=0;i<n;i++)cin>>a[i];
InsertSort(a,n);
for(int i=0;i<n/2;i++)s1+=a[i];
for(int i=n/2;i<n;i++)s2+=a[i];
cout<<s2-s1;
}



Условия задач взяты с сайта acmp.ru