主题：第75次比赛题目
fenix124 [专家分：70] 发布于 2008-10-27 11:32:00
昨天fenix124带着他的未来女朋友去逛香山，非常遗憾他们没有看见红叶，很多枫树都是绿的。
题目就是建立一种模型让你计算一下什么时候去香山比较好。模型如下:
假设每棵树的美观都对应着一个数值。绿叶比较多的时候值为正，当它完全变红的时候为0，如果红叶慢慢掉落就成为负的了。
当红叶掉完了，它的美感值就固定了。枫树的美感值变化快慢程度不同，有些2天变化一下，而其他的可能会慢些。
看枫叶最好的时候是所有枫叶尽量接近红色，就是所有美感值的绝对值之和最小。
Input:
第一行N,枫树的棵树，小于1000。
接下来的N行，每行四个数Bi,Ti,Ci,Di，表示每棵枫树的初始美观值，美观值变化的周期，每个周期美感值减少量，以及美感值的下限,为一个负数(也就是到这个时候就不会减了)。
为了使题目简单,所有数绝对值小于100000，保证所有树在100天内树叶掉光。
output:
输出看枫叶的最好时候(如果多个相同，输出最早的那天)，以及枫叶的美观值绝对值之和。
sample:
输入:
3
5 2 3 -100
10 4 5 -20
-5 3 3 -9
输出:
经过我的小程序枚举，貌似是
4 14
时间和价值的函数一部分如下:
0 20
1 20
2 17
3 20
4 14
5 14
6 18
7 18
8 16
9 16
10 19
11 19
12 27
13 27
14 30
15 30
16 38
17 38
18 41
19 41
20 49
本周五给出比赛结果
最后更新于：2008-10-31 20:26:00
回复列表 （共6个回复）
沙发
tigerset [专家分：80] 发布于 2008-10-27 13:45:00
#include<iostream>
using namespace std;
void red(int N,int B[],int T[],int C[],int D[])
{
int temp;//判断D[]是否全到达美感最小值
int Tcount=0;//保存所有美感值的绝对值之和最小的周期值
int value=0;//保存所有美感值的绝对值之和最小的的美感值
int count=0;//周期值
int k;//美感值绝对值
int sum;//当前美感值绝对值之和
int *M=new int[N];//存储当前美感值
for(int i=0;i<N;i++)
{
k=(B[i]>0?B[i]:-B[i]);
value+=k;
M[i]=B[i];
}
for(;;)
{
temp=0;
sum=0;
count++;
for(int j=0;j<N;j++)
{
if(M[j]!=D[j])//当前美感值未达到下限
{
if((count%T[j])==0) M[j]-=C[j];//到达变化周期
if(M[j]<D[j]) M[j]=D[j];
}
k=(M[j]>0?M[j]:-M[j]);
sum+=k;
if(M[j]==D[j]) temp++;
}
if(sum<value) {//取美感绝对值最小
Tcount=count;
value=sum;
//cout<<count<<" "<<sum<<endl;
}
if(temp==N) break;
//cout<<count<<" "<<sum<<endl;
}
cout<<Tcount<<" "<<value<<endl;
}
int main()
{
int n=3;
cin>>n;
int *B=new int[n];//初始美观值
int *T=new int[n];//美观值变化的周期
int *C=new int[n];//每个周期美感值减少量
int *D=new int[n];//以及美感值的下限
for(int i=0;i<n;i++)
cin>>B[i]>>T[i]>>C[i]>>D[i];
red(n,B,T,C,D);
return 1;
}
板凳
mht@ [专家分：1260] 发布于 2008-10-27 19:06:00
#include <iostream>
using namespace std;
struct N75
{
int Bi; //初值
unsigned int Ti; // 周期
unsigned int Ci; //减少量
int Di; // 最小值
int flag; //是否到Di的标志
int Pi; //当前值
};
void A(N75 FengShu[],int N)
{
int min=0x0FFFFFFF,sum,min_N=0;
std::cout<<"穷举所有："<<std::endl;
int k=0;
for(int i=0;;i++)
{
sum=0;
for(int j=0;j<N;j++)
{
FengShu[j].Pi=FengShu[j].Bi-i/FengShu[j].Ti*FengShu[j].Ci;
if(FengShu[j].flag==0)
{
if(FengShu[j].Pi<=FengShu[j].Di)
{
FengShu[j].flag=1;
FengShu[j].Pi=FengShu[j].Di;
k++;
sum+=abs(FengShu[j].Di);
}
else
sum+=abs(FengShu[j].Pi);
}
else
sum+=abs(FengShu[j].Di);
}
if(min>sum)
{
min=sum;
min_N=i;
}
std::cout<<i<<" "<<sum<<std::endl;
if(k==N)
break;
}
std::cout<<"\n最小的情况："<<std::endl;
std::cout<<min_N<<" "<<min<<std::endl;
}
int main()
{
int N;
struct N75 *FengShu;
std::cout<<"输入枫树的数量：\n";
std::cin>>N;
FengShu=(N75*)malloc(sizeof(N75)*N);
for(int i=0;i<N;i++)
{
std::cin>>FengShu[i].Bi;
std::cin>>FengShu[i].Ti;
std::cin>>FengShu[i].Ci;
std::cin>>FengShu[i].Di;
FengShu[i].Pi=FengShu[i].Bi;
FengShu[i].flag=0;
}
A(FengShu, N);
return 0;
}
首先，我是个初学者，刚进论坛什么还不懂，也来参与参与
主要是想了解一下这个比赛的制度，一般什么时间发布，怎么发布的。
至于这个程序的效率问题，我没考虑过，还请高手们指点
3 楼
fenix124 [专家分：70] 发布于 2008-10-27 21:14:00
//把数据改小枚举的感觉真他妈的爽
#include <stdio.h>
int N;
int B[1005];
int T[1005];
int C[1005];
int D[1005];
inline int abs(int x)
{
if(x < 0) x = -x;
return x;
}
int getCurrentValue(int i,int t)
{
int value;
value = B[i] - t/T[i]*C[i];
if(value < D[i])
{
value = D[i];
}
return abs(value);
}
void solve()
{
int i,j;
int best,bestday;
int totalvalue;
best = 0xfffffff;
for(i = 0;i <= 100;i++)
{
totalvalue = 0;
for(j = 0;j < N;j++)
{
totalvalue += getCurrentValue(j,i);
}
if(totalvalue < best)
{
best = totalvalue;
bestday = i;
}
}
printf("%d %d\n",totalvalue,bestday);
}
int main()
{
int i;
scanf("%d",&N);
for(i = 0;i < N;i++)
{
scanf("%d%d%d%d",B+i,T+i,C+i,D+i);
}
solve();
return 0;
}
4 楼
zhangyuke [专家分：0] 发布于 2008-10-28 11:48:00
[code=c]
#include<iostream.h>
#include <math.h>
/**********************************
*定义用于记录每课课枫叶树的结构体
************************************/
typedef struct tree{
short init;
short priod;
unsigned short decr;
short limit;
}Tree,*pTree;
/************************************************************
*名称：high_point
*功能:计算每一天所有枫叶树美观值得绝对值之和。
*参数：a 结构体Tree的数组，包含每课树的信息
n 枫叶树的数量
result 记录一百天之内每天所有枫叶树美观值得绝对值之和。
**************************************************************/
void high_piont(Tree a[],int n,short result[])
{
int m=0;
for (int i=0;i<100;i++)
{
for (int j=0;j<n;j++)
{
if((i!=0)&&(i%a[j].priod==0)&&(a[j].init>=(a[j].limit+a[j].decr)))
a[j].init-=a[j].decr;
result[m]+=abs(a[j].init);
}
m++;
}
}
/***************************************************************
*名称：findMin
*功能：找出所有枫叶树美观值绝对值之和最小的一天。
*参数：a 记录每天所有枫叶树美观值绝对值之和。
******************************************************************/
void findMin(short a[])
{
int temp;
temp=a[0];
int m=0;
for (int i=1;i<100;i++)
{
if(a[i]<temp)
{
temp=a[i];
m=i;
}
}
cout<<"The result is: "<<m<<" "<<temp<<endl;
}
void main()
{
short n;
short result[100];
for (int i=0;i<100;i++) //初始化数组
result[i]=0;
pTree pTree;
cout<<"please input the number of trees:"<<endl;
cin>>n;
pTree=new Tree[n]; //分配地址
cout<<"please input the information of each tree:"<<endl;
for ( i=0;i<n;i++)
{
cin>>pTree[i].init>>pTree[i].priod>>pTree[i].decr>>pTree[i].limit;
}
high_piont(pTree,n,result);
findMin(result);
/* for (i=0;i<20;i++)
{
cout<<i<<" "<<result[i]<<endl;
}*/
delete pTree;
}
[/code]
5 楼
zhangyuke [专家分：0] 发布于 2008-10-30 22:21:00
怎么没几个人回帖啊，都忙啥去了？
6 楼
yj1221 [专家分：20] 发布于 2008-10-31 08:37:00
#include <iostream.h>
#include <fstream.h>
#include <math.h>
int getSum(int **a, int n); // get the sum value of tree
bool testValue(int **a, int n); // if a[0..n-1][0] has a tree can make leaves , return true;
void changeValue(int **a, int n, int day); // change value by day
int main()
{
ifstream in("c:\\in.txt");
int row;
in >> row;
int **value = new int *[row];
for(int i = 0; i < row; i++)
{
value[i] = new int [4];
for(int j = 0; j < 4; j++)
in >> value[i][j];
}
int sum = 0;
sum = getSum(value, row);
int day = 1;
int thisDay = day;
while( testValue(value, row) )
{
changeValue(value, row, day);
int tmp = getSum(value, row);
if( tmp < sum)
{
sum = tmp;
thisDay = day;
}
day++;
}
cout << "this day is " << thisDay << endl;
cout << "sum is " << sum << endl;
return 0;
}
int getSum(int **a, int n)
{
// get the sum value of tree
int sum = 0;
for(int i = 0; i < n; i++)
sum += abs(a[i][0]);
return sum;
}
bool testValue(int **a, int n)
{
// if a[0..n-1][0] has a tree can make leaves , return true;
for(int i = 0; i < n; i++)
{
if( a[i][0] > a[i][3])
return true;
}
return false;
}
void changeValue(int **a, int n, int day)
{
// change value by day
for(int i = 0; i < n; i++)
{
if( day%a[i][1] == 0 && a[i][0] > a[i][3])
{
a[i][0] -= a[i][2];
if(a[i][0] < a[i][3])
a[i][0] = a[i][3];
}
}
}
我来回复
您所在位置：