Java超时??

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 条评论

  • @ 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

信息

ID
1097
难度
6
分类
贪心 点击显示
标签
递交数
23854
已通过
6310
通过率
26%
被复制
41
上传者