- 合并果子
- 2015-05-11 22:34:23 @
import java.io.*;
import java.util.*;
public class Main
{
public static void main(String[] args)
{
// TODO Auto-generated method stub
Scanner input = new Scanner(System.in);
int n = input.nextInt();
int cin = 0;
ArrayList<Integer> a = new ArrayList<Integer>();
for (int i = 0; i < n; i++)
{
cin = input.nextInt();
a.add(cin);
}
Collections.sort(a);
for (int i = 0; i < n - 1; i++)
{
a.set(0, a.get(0) + a.get(1));
a.remove(1);
Collections.sort(a);
}
int ans = a.get(0) + n;
System.out.println(ans);
}
}
4 条评论
-
CWW LV 8 @ 2015-05-24 00:51:13
你这太暴力了,要不你建树,要不优先队列
-
2015-05-22 20:02:22@
我C++的STL优先队列只用了90ms,不到300KiB啊
#include<cstdio>
#include<queue>
using namespace std;
#define IOFileName "P1097"
int n,ai,x,y,ans=0;
priority_queue<int,deque<int>,greater<int> >a;//就是这货
int main(){
//freopen(IOFileName".in","r",stdin);
//freopen(IOFileName".out","w",stdout);
scanf("%d\n",&n);
for(int i=0;i<n;i++){
scanf("%d ",&ai);
a.push(ai);
}
while(a.size()>1){
x=a.top();a.pop();
y=a.top();a.pop();
a.push(x+y);
ans+=x+y;
}
printf("%d\n",ans);
} -
2015-05-12 18:06:26@
用Java的优先队列,越小的整数优先级越大,每次取出最小的两个,合并,放进去它们的和,更新一下答案就行了。
-
2015-05-12 13:37:47@
这个做法不是Java也要超时。
- 1