تحدي برمجي[012][متوسط] بطارية الالة الحاسبة
صديقك لديه مجموعة من الأعداد يريد معرفة حاصل ضربهم ، سيستخدم الالة الحاسبة بالطبع.
عند ضرب أي عددين تستهلك الالة الحاسبة مقدار مضروبهما من الطاقة مثلا إذا كان لديك عددان x و y وقمت بضربهما باستخدام الالة الحاسبة فإن طاقتها ستنقص بمقدار x * y
بما أنك مبرمج طلب منك صديقك المساعدة فهل يمكنك أن تساعده؟
المدخلات
اول سطر يحتوي على عدد N
في السطر التالي يأتي N عدد
1 <= N <= 10^6
1 <= x, y <= 10^9
المخرجات
اقل قدر من الطاقة يمكن استهلاكه لضرب جميع الأعداد
مثال
لنأخذ كمثال هذا المدخل
4
3 2 10 7
المخرجات
468
التوضيح
هذا افضل ترتيب يمكن به ضرب الأعداد أي طريقة غير هذه ستؤدي لإستهلاك طاقة أكبر
min_energy = 0
3 * 2 = 6
min_energy = 6
6 * 7 = 42
min_energy = 42 + 6 = 48
10 * 42 = 420
min_energy = 420 + 48 = 468
cc
هل يمكنك إرفاق testcase أكبر ؟
from bisect import insort_left
def k(f):
s = 0
while len(f) != 1:
p = f.pop(0) * f.pop(0)
s += p
insort_left(f, p)
print(s)
raw_input()
a = list(map(int, raw_input().split()))
a.sort()
k(a)
حلك صحيح
حلك يعمل في
O(N^2 log N)
افضل حل يعمل في n log n وهو كالتالي:
في اي مرحلة نريد ضرب أصغر عددين وإدخال الناتج في القائمة بحيث تكون مرتبة. يمكن تنفيذ هذه العملية بكفاءة بإستخدام heap تحديدا min heap
عملية إنشاء ال heap تعمل في n log n و ضرب الأعداد n log n الناتج n log n
الحل ببايثون
from heapq import heappush, heappop
heap = []
n = input()
for i in map(int, input().split()):
heappush(heap, i)
energy = 0
while len(heap) > 1:
mul = heappop(heap) * heappop(heap)
energy += mul
heappush(heap, mul)
print(energy)
لمن هو مهتم هذا الحل ب c++
#include <iostream>
#include <queue>
using namespace std;
int main(){
int n;
cin >> n;
int x;
priority_queue<int> pq;
while(n--){
cin >> x;
pq.push(-x);
}
int a, b;
int energy = 0;
while(pq.size() > 1){
a = pq.top(); pq.pop();
b = pq.top(); pq.pop();
energy += a * b;
pq.push(-(a * b));
}
cout << energy;
return 0;
}
شكراً على المشاركة بالحل، لم أفكر بإستعمال min heap، نسيت أغلب Data structures.
insort تقوم بعمل binary search، المشكل انني أقوم بعمل pop(0) (كمبليكستي او(N)) إذاً صحيح كما قلت أنت O(N^2 log N) أحسنت، ولكن يمكن أن تكون O(N log N) إذا تم إستعمال stack و- binary search، شكراً مرة أخرى على مشاركة الحل.
لا أعرف لماذا لكن حلك الذي يعمل بال-min heap أسرع من BS + stack
def reverse_insort(a, x, lo=0, hi=None):
"""Insert item x in list a, and keep it reverse-sorted assuming a
is reverse-sorted.
If x is already in a, insert it to the right of the rightmost x.
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"""
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
if x > a[mid]: hi = mid
else: lo = mid+1
a.insert(lo, x)
def k(f):
s = 0
while len(f) != 1:
p = f.pop() * f.pop()
s += p
reverse_insort(f, p)
print(s)
a = range(1, 10 ** 5)
a.sort(reverse=True)
k(a)
$ /usr/bin/time -v python /home/mo/a.py > /dev/null
Command being timed: "python /home/mo/a.py"
User time (seconds): 5.83
System time (seconds): 0.14
Percent of CPU this job got: 99%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:05.99
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 10576
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 2612
Voluntary context switches: 1
Involuntary context switches: 96
Swaps: 0
File system inputs: 0
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0
-
$ cat b.py
from heapq import heappush, heappop
heap = []
for i in xrange(1, 10 ** 5):
heappush(heap, i)
energy = 0
while len(heap) > 1:
mul = heappop(heap) * heappop(heap)
energy += mul
heappush(heap, mul)
print(energy)
$ /usr/bin/time -v python /home/mo/b.py > /dev/null
Command being timed: "python /home/mo/b.py"
User time (seconds): 4.10
System time (seconds): 0.00
Percent of CPU this job got: 99%
Elapsed (wall clock) time (h:mm:ss or m:ss): 0:04.11
Average shared text size (kbytes): 0
Average unshared data size (kbytes): 0
Average stack size (kbytes): 0
Average total size (kbytes): 0
Maximum resident set size (kbytes): 10688
Average resident set size (kbytes): 0
Major (requiring I/O) page faults: 0
Minor (reclaiming a frame) page faults: 2589
Voluntary context switches: 1
Involuntary context switches: 67
Swaps: 0
File system inputs: 0
File system outputs: 0
Socket messages sent: 0
Socket messages received: 0
Signals delivered: 0
Page size (bytes): 4096
Exit status: 0
ملاحظة bisect ليس فيه reverse
التعليقات