主题：60次编程比赛
FancyMouse [专家分：13680] 发布于 2007-08-22 12:03:00
原60次的出题人要伸张出题权请联系我or斑猪
题大家肯定见过，数据范围肯定没见过。以上
结束时间[color=FF0000]8/25 20:00[/color]
[url=http://www.programfan.com/club/post-247561.html]答疑帖[/url]
重申，本帖禁水，要水请到[url=http://www.programfan.com/club/post-247561.html]答疑帖[/url]去
题：-----------------------------------------------------------
Problem
有n堆苹果，每次可以将两堆合并为一堆，这次操作消耗的体力是这两堆苹果数之和。最终需要将n堆苹果合并为一堆，问最少要多少体力？
这些苹果十分特殊：一开始的时候第i堆苹果有i个苹果,i=1,2,...,n
嘛，我会先在n<=5,000评测，再在n<=50,000评测，最终级别是n<=[color=FF0000]500,000,000[/color]。当然，[color=FF0000]时限不变[/color]。
Input
从控制台输入一个正整数n
Output
一行一个数，表示需要的最少体力，保证答案<2^63
Sample Input
2
Sample Output
3
Limits
时限：1s。内存限：64MB
评测参数：-----------------------------------------------------
评测cpu：Celeron 2.4G
C++选手禁用STL
禁止一切系统操作和文件读写
c/c++编译器默认采用g++。望选手能根据编译器修改自己的代码
追加：Windows下的g++是用mingw32，所以%lld标识符请换用%I64d以达到正确的答案。对于未修改的我会在评测前手动修改，不影响成绩
---------------------------------------------------------------
本次评测将采用半自动评测方式，如果遇到编译错误我尽量修改为可编译通过的代码（影响成绩）。具体评测规则将在成绩公布帖中公布
最后更新于：2007-08-25 13:49:00
回复列表 （共16个回复）
11 楼
jacob007 [专家分：70] 发布于 2007-08-23 13:44:00
#include <iostream.h>
int* generate(unsigned int size);
void sort(int* begin, int* end);
int getMinEnergy(int* array, int* begin, int* end);
int getResult(int appleArrayNum);
void main()
{
int appleArrayNum = 0;
cin>>appleArrayNum;
cout<<getResult(appleArrayNum)<<endl;
};
int* generate(unsigned int size)
{
int* array = new int[size];
for (unsigned int i = 0; i < size; i++)
array[i] = i+1;
return array;
}
void sort(int* begin, int* end)
{
int target = *begin;
int *dest;
int *temp;
for (dest = begin+1; dest <= end; dest++)
{
if (target < *dest)
break;
};
for (temp = begin; temp < dest-1; temp++)
*temp = *(temp+1);
*temp = target;
};
int getMinEnergy(int* begin, int* end)
{
int result = 0;
while(begin != end)
{
*(begin+1) += *begin;
begin++;
result += *begin;
sort(begin, end);
};
return result;
};
int getResult(int appleArrayNum)
{
int *array = generate(appleArrayNum);
int result = getMinEnergy(array, array+appleArrayNum-1);
delete[] array;
array = NULL;
return result;
}
不知道这个算法效率高不高
12 楼
isjk [专家分：210] 发布于 2007-08-23 16:17:00
#include<iostream>
int main()
{
long long n,m;
while(cin>>n)
{
m = n;
n *= n;
n += m;
n >>= 1;
std::cout<<n<<std::endl;
}
return 0;
}
13 楼
flushtime [专家分：200] 发布于 2007-08-23 17:14:00
[code=c]
/**
时间复杂度为n*log(n)的算法，其实就是huffman编码
但没有用到第k堆苹果为k的条件，貌似n>500000就搞不定了。faint~
@author Eastsun
@version 1.0 2008/2/23
*/
#include<iostream>
typedef long long bint;
using namespace std;
void heapAdjust(bint* value,long size){
long pos =1;
bint item =value[pos];
for(long index =pos<<1;index<=size;index <<=1){
if(index<size&&value[index]>value[index+1]) index ++;
if(item <=value[index]) break;
value[pos] =value[index];
pos =index;
}
value[pos] =item;
}
bint solve(long size){
bint *value =new bint[size+1];
for(long index=size;index>0;index--) value[index] =index;
bint power =0;
while(size>=2){
bint a =value[1];
value[1] =value[size--];
heapAdjust(value,size);
int b =value[1];
value[1] =a + b;
heapAdjust(value,size);
power += a + b;
}
delete[] value;
return power;
}
int main(){
long size;
cin>>size;
cout<<solve(size)<<endl;
return 0;
}[/code]
14 楼
marginal4 [专家分：0] 发布于 2007-08-24 17:37:00
想看看写的什么！
15 楼
AntiMicrosoft [专家分：3740] 发布于 2007-08-25 02:53:00
把所有要处理的1～n看成一个队列
维护一个动态大小的小顶堆
队首前两个元素以及堆中顶端的3个元素中取和最小的合并
删除堆中或者队列中取出的结点 将合并后的结果插入堆中 调整这个堆 使之保持为小顶堆
由于队列的特殊形式 可以不作存储 在边界处理上可以优化一下 减少不必要的判断
核心思想: 小顶堆+最优哈夫曼编码
16 楼
eagle37 [专家分：40] 发布于 2007-08-25 13:12:00
#include <stdio.h>
#include <stdlib.h>
// this method get the most significant bit of num,
// exp keeps the bit,
// r keeps the rest,
// require that num>0&&num<2^31;
void getExp(long long num,long long *r,int *exp){
long long t=1<<30;
*exp=30;
while(!(t&num)){
(*exp)--;
t=t>>1;
}
*r=num-t;
}
// get the cut position of num
// m keeps the cut position
// exp keeps the most significant bit
// flag keeps a flag
void getCutPosition(long long num,long long *m,int *exp,int *flag){
*m=num/6;
long long temp=0;
long long r=0;
if(*m*6==num){
*flag=1;
(*m)++;
temp=num-2*(*m);
getExp(temp,&r,exp);
*flag=(r+1)%2;
*m=(*m)*3;
*m+=r*3/2;
}
else if(*m*6+3>=num) {
*flag=0;
temp=num-2*(*m)-1;
getExp(temp,&r,exp);
*flag=r%2;
(*m)=(*m)*3+1;
*m+=r*3/2;
}
else{
*flag=1;
(*m)++;
temp=num-2*(*m);
getExp(temp,&r,exp);
*flag=(r+1)%2;
*m=(*m)*3;
*m+=r*3/2;
}
}
void getResult(long long num,long long *result){
*result=0;
int flag=0;
long long m;
int exp=0;
getCutPosition(num,&m,&exp,&flag);
if(!flag){//when the cutposition is 3m+1 and 3m+2
*result=(m+1)*(m+2);
*result-=(m+2)*(m+2)/3;
}
else{//when the cutposition is 3m and 3m
*result=(m+1)*m;
*result-=(m/3)*m;
}
*result+=(1+num)*num/2*exp;
}
int main(){
long long num=0;
long long result=0;
puts("input");
scanf("%lld",&num);
if(num<=0){printf("error\n"),exit(1);}
if(num==1)result=0;
else getResult(num,&result);
printf("output\n%I64d\n",result);
return 0;
}
我来回复
您所在位置：