暖色记忆

NC248436. 暖色记忆

描述

《暖色记忆》

心灵的橱窗

陈设着一个又一个纪念品

我细数这些珍宝

小心翼翼

拭去上面的灰尘

那一次故意安排的不期而遇

那一双始终注视你的侧影的眼睛

缟衣下清秀的容颜

填补了年少的我的每个梦境

时光荏苒而逝

暖色的记忆早已把我淹没

我宁可沉溺其中

倾尽我的一切

也要延后那注定消逝的命运

小红拿到了一个长度为 $n$ 的数组（保证 $n$ 为偶数），她将进行如下操作：
1. 选择一个元素，将其染红。
2. 选择一个未被染红的元素，将其删除。
3. 使得所有被染红的元素除以2，向下取整。

小红将进行 $n/2$ 次操作，操作后数组将剩下 $n/2$ 个染红的元素。小红希望这 $n/2$ 个数的和尽可能大，你能帮帮她吗？

输入描述

第一行输入一个正整数，代表数组的大小。
第二行输入个正整数，代表数组的元素。

输出描述

小红操作结束后，最后元素之和的最大值。

示例1

输入:

4
1 2 3 4

输出:

说明:

先选择第二个数染红，删除第一个数，然后将染红的数除以2，数组变成 $[\color{red}{1}$ $,3,4]$
然后选择将4染红，删除3，然后将染红的数除以2，数组变成 $[\color{red}0,\color{red}2]$

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++ 11.0.1) 解法, 执行用时: 53ms, 内存消耗: 1180K, 提交时间: 2023-02-14 22:06:48

#include<bits/stdc++.h>
using namespace std;
long long n,a[200002],i,b=2,s;
int main()
{
	cin>>n;
	for(i=1;i<=n;i=i+1)cin>>a[i];
	sort(a+1,a+n+1);
	for(i=n;i>max(n/2,n-40);i=i-1)
	{
		s=s+a[i]/b;
		b=b*2;
	}
	cout<<s;
	return 0;
}

pypy3 解法, 执行用时: 156ms, 内存消耗: 33260K, 提交时间: 2023-02-14 19:33:53

n=int(input())
a=sorted(map(int,input().split()))
res=0
for i in range(1,n//2+1):
    res+=a.pop()>>i
print(res)

Python3 解法, 执行用时: 117ms, 内存消耗: 15744K, 提交时间: 2023-02-23 17:15:58

n=int(input())>>1
print(sum(x>>i+1 for i,x in enumerate(sorted(list(map(int,input().split())))[n:][::-1])))

上一题

下一题

详情