没有调试过。
#define N (10) //set the total station
#define OIL_PER_KM (1)
#define INIT_OIL (5)
#define MAX_CONTAINER (100)
struct station
{
float dist;
float price;
};
float curr;
struct station st[N];
void init_station()
{
//int i;
curr = INIT_OIL;
//initilize the station information
st[0].dist = 0;
st[N].price = MAX_LONG;
//otherinformation should be filled according to the actually.
}
// 0 -- for increment always
// 1 == exist decrement,but the low state's prices is higher the the from state
// -1 -- the last station
int check_state(int from,int to,int &ret)
{
int i ;
int retValue = 0;
if(from == to) {
return -1;
}
for(i = from ; i < to ; i ++) {
if(st[i].price > st[i + 1].price) {
if(st[i + 1].price > st[from].price) {
retValue = 1;
} else {
retValue = 2;
}
ret = i + 1;
break;
}
}
return retValue;
}
float get_oli(int from,int to)
{
int i;
float total = 0.0;
if(from == to) {
return total;
}
for(i =from ; i <= to ; i ++) {
total += st[i].dist;
}
return (total * OIL_PER_KM);
}
float try_search()
{
int i ,j, retValue,newIndex;
float tmp, cost = 0;
do{
curr -= st[i].dist * OIL_PER_KM;
if(st[i].price >= st[i + 1].price) {
tmp = get_oli(i,i+1);
cost += (tmp - curr) * st[i].price;
curr = tmp;
i ++;
} else {
for(j = i + 1; j < N - 1; j ++) {
tmp = MAX_CONTAINER;
tmp -= st[j].dist * OIL_PER_KM;
if(tmp < 0) {
break;
}
}
//this is the station we can reach,if the
j --;
retValue = check_state(i,j,newIndex);
if(retValue == 0) {
cost += (MAX_CONTAINER - curr) * st[i].price;
curr = MAX_CONTAINER ;
i ++;
} else if(retValue == 1) {
tmp = get_oli(i,newIndex);
cost += (tmp - curr) * st[i].price;
curr = tmp;
i = newIndex;
} else {
tmp = ( st[i +1].dist * OIL_PER_KM - curr);
if(tmp > 0 ) {
cost += tmp * st[i].price;
}
i ++;
}
}
}while(i < N -1);
return cost;
}
[返回] 计算机科学论坛 →
计算机理论与工程 → 『 算法理论与分析 』 → 求解"加油问题"
(订阅本版)
2006/10/24 22:15:00
新浪微博
求解"加油问题"
