n რაოდენობის სლაიმი არის თითოეულ რიგში , თითო სლაიმს მინიჭებული აქვს მთელი რიცხვი(შეიძლება იყოს უარყოფითიც და 0-ც), თითოეულ სლაიმს შეუძლია რომ შეჭამოს მის გვერდით მყოფი სლაიმი. როცა სლაიმი ,რომლის მნიშვნელობაც არის x ჭამს სლაიმს რომლის მნიშვნელობაც არის y , შეჭმული სლაიმი ქრება და დარჩენილ სლაიმს ენიჭება მნიშვნელობა x-y .
სლაიმები ერთმანეთს ჭამენ ,სანამ არ დარჩება ერთი სლაიმი.
იპოვეთ მაქსიმალური შესაძლო მნიშვნელობა დარჩენილი სლაიმის.
შემომავალი მნიშვნელობები:
პირველად შემოდის მთელი რიცხვი n (1<=n<=500000) სლაიმების რაოდენობას აღნიშნავს.
შემდეგი ხაზი შეიცავს n მთელ რიცხვს, თითოელი აღნიშნავს სლაიმების მნიშვნელბებს (-10^9<=ai<=10^9) ai არის i სლაიმი.
გამომავალი მნიშვნელობა:
მხოლოდ ერთი მთელი რიცხვი-მაქსიმალური შესაძლო მნიშვლენობა დარჩენილი სლაიმის.
მაგალითი:
input
4
2 1 2 1
output
4
თითოეული სლაიმი ან ემატება საბოლოო პასუხს ან აკლდება, ამიტომაც თითოეულ სლაიმს ვანიჭებთ + ან – იმის აღსანიშნავად თუ რამდენად დაემატება ან დააკლდება საბოლოო პასუხს მოცემული სლაიმი.
მთავარი გასაღები ამოცანის გადასაჭრელად არის ის რომ ყველა კომბინაცია (+/-)-ების არის მიღწევადი, გარდა ერთდროულად ყველა +-სა და ერთდროულად ყველა (-)-სა , რათქმა უნდა როცა n!=1-ს, როცა n=1-ს პასუხი თავად ეს სლაიმია.
თუ მოცემული მასივი შეიცავს რიცხვებს გვაქვს 0-სგან განსხვავებული დადებითი და უარყოფითი რიცხვები ,მაშინ ჩვენ შეგვიძლია მათი აბსოლიტური მნიშვნელობის პირდაპირ შეკრება(+ დავწერთ დადებითი რიცხვების წინ, და -ებს უარყოფითების წინ)
თუ მასივი შეიცავს მხოლოდ დადებით რიცხვებს, მაშინ – ვუწერთ მხოლოდ უმცირესი მნიშვნელობის მქონეს, და + დანარჩენს, იმავე ნაირად ვიქცევით უარყოფითი რიცხვებისთვის, + ვუწერთ უმცირესს (მოდულით). ალგორითმის სირთულე არის O(n)
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "n"
#define int long long
const int N=5e5+5;
int n, minval=1e9, ans=0;
int a[N];
bool checkpos=0, checkneg=0;
int32_t main()
{
IOS;
cin>>n;
if(n==1)
{
int k;
cin>>k;
cout<<k;
exit(0);
}
for(int i=1;i<=n;i++)
{
cin>>a[i];
minval=min(abs(a[i]), minval);
checkpos|=(a[i]>=0);
checkneg|=(a[i]<=0);
ans+=abs(a[i]);
}
if(checkpos&&checkneg)
cout<<ans;
else
cout<<ans-2*minval;
return 0;
}
ციკლში თანდათან კითხულობს სლაიმების მნიშვნელობებს, და თან მათ აბსოლიტურს უმატებს პასუხს და ასევე ინახავს მოდულით უმცირეს მნიშვნელობას, თუ (+/-) გვქონდა მაშინ პირდაპირ წერს პასუხს, თუ არადა აკლებს მინიმალურ მნიშვნელობას (2-ჯერ რადგან ერთხელ მიუმატა ციკლში).