線上訂房服務-台灣趴趴狗聯合訂房中心
發文 回覆 瀏覽次數:1225
推到 Plurk!
推到 Facebook!

10612 Shoemaker's Problem

尚未結案
kill22890
一般會員


發表:1
回覆:0
積分:0
註冊:2013-01-29

發送簡訊給我
#1 引用回覆 回覆 發表時間:2013-01-29 19:01:51 IP:114.41.xxx.xxx 訂閱
丟到線上測試系統wrong answer, 請各位幫忙找Bug,
我目前認為自己的程式結果正確, 不知還有哪個地方未考慮?
題目預設最多有1000個job, 每個job最多罰金10000, 故預設罰金total_fine=10000000。

為了詳細讓各位了解問題, 我將程式碼貼出, 可自行下載,
主要功能其實只有在void Permutation, 其為列出所有排列遞迴,
然後依據順序判斷總罰金, 只要找到排列順序小於目前預設就取代當前order。

因為線上測試系統(Linux), 限制格式眾多, C 無法使用itoa, 所以使用stringstream, 轉換完成後再存入string,
order部分使用strcat串接其順序。

Word .docx說明:
http://uva.onlinejudge.org/external/100/10026.html

code:
https://docs.google.com/a/gm.nfu.edu.tw/file/d/0B5vtp-1Q8laRX1B5VlF5c1JFT00/edit

線上測試系統:
https://gpe2.acm-icpc.tw//showproblemtab.php?probid=10612&cid=130


int total_fine;
char order[2000];
//initial k is 0.
void permutation(vector<struct node> &iv, unsigned k)
{
int tmp_fine=0, pre_days=0;
char tmp_order[2000], copy_order[2000], copy_tmp_order[2000], *p1, *p2;
memset
(tmp_order,'\0',sizeof(tmp_order));
vector
<struct node>::iterator iter;

if(k == iv.size()-1)
{
for(iter=iv.begin() ; iter!=iv.end() ; iter )
{
tmp_fine
=pre_days*iter->fine;
pre_days
=iter->days;
strcat
(tmp_order,iter->number.c_str());
strcat
(tmp_order," ");
}
//監看各種排列總罰金
/*
cout
<<"tmp_fine: "<<tmp_fine<<' ';
cout
<<"total_fine: "<<total_fine<<' ';
cout
<<"tmp_order: "<<tmp_order<<' ';
cout
<<"order: "<<order<<endl<<endl;
*/
if(tmp_fine<total_fine)
{
total_fine
=tmp_fine;
strcpy
(order,tmp_order);
}
else if(tmp_fine==total_fine)
{
strcpy
(copy_order,order), strcpy(copy_tmp_order,tmp_order);
p1
=strtok(copy_order," ");
p2
=strtok(copy_tmp_order," ");
while(1)
{
if(p1==p2)
{
p1
=strtok(NULL," ");
p2
=strtok(NULL," ");
continue;
}
else if(atoi(p1)>atoi(p2))
{
strcpy
(order,tmp_order);
break;
}
else break;
}
}
}
else
{
for(unsigned i=k ; i<iv.size() ; i )
{
swap
(iv[i],iv[k]);
permutation
(iv,k 1);
swap
(iv[i],iv[k]);
}
}
}


編輯記錄
kill22890 重新編輯於 2013-01-29 04:02:54, 註解 無‧
kill22890 重新編輯於 2013-01-29 04:11:12, 註解 無‧
kill22890 重新編輯於 2013-01-29 04:20:26, 註解 無‧
kill22890 重新編輯於 2013-01-29 05:12:13, 註解 無‧
系統時間:2017-10-24 2:56:56
聯絡我們 | Delphi K.Top討論版
本站聲明
1. 本論壇為無營利行為之開放平台,所有文章都是由網友自行張貼,如牽涉到法律糾紛一切與本站無關。
2. 假如網友發表之內容涉及侵權,而損及您的利益,請立即通知版主刪除。
3. 請勿批評中華民國元首及政府或批評各政黨,是藍是綠本站無權干涉,但這裡不是政治性論壇!