Welcome to Leon's Blog

日歷

2008年7月

日

一

二

三

四

五

六

統(tǒng)計(jì)

隨筆 - 30
文章 - 0
評(píng)論 - 51
引用 - 0

導(dǎo)航

常用鏈接

留言簿(4)

隨筆分類(lèi)

隨筆檔案

ACM

搜索

閱讀排行榜

評(píng)論排行榜

acm pku 1010 程序

今天早上終于提交成功了！這道題做了有一個(gè)星期多了，老是找不到原因。今天在偶然間發(fā)現(xiàn)了，先將代碼貼出來(lái)，還請(qǐng)大家指正！感謝steven和一個(gè)匿名網(wǎng)友的建議，謝謝你們！但是程序運(yùn)行的時(shí)間還是過(guò)長(zhǎng)，希望大家能夠幫助修改。

#include <stdio.h>
2

#include <string.h>
3

#include <stdlib.h>
4

int result[4];
7

int reNumber, reCount, tie, reMax; //result是最終客戶(hù)的郵票種類(lèi)，reCount是客戶(hù)郵票總個(gè)數(shù)，reNumber是客戶(hù)不同郵票的個(gè)數(shù)
8

int GetNumber(int *stamp, int *customer, int *stampNumber, int *customerNumber) //獲取郵票和客戶(hù)信息。
10

{
11

int i, n,count[100]; // count在這里起到一個(gè)優(yōu)化的作用。
12

n = 0;
13

(*stampNumber) = 0;
14

memset(count, 0 ,sizeof(int)*100);
15

while(1) //收集關(guān)于郵票的面值。
16

{
17

if(scanf("%d", &n) == EOF)
18

return -1;
19

if(n == 0)
20

break;
21

if(count[n]++ < 5)
22

stamp[(*stampNumber)++] = n;
23

}
24

//stampNumber--;
25

(*customerNumber) = 0;
26

while(1)
27

{
28

scanf("%d", &n); //收集關(guān)于客戶(hù)需要郵票的總面值數(shù)。
29

if(n == 0)
30

break;
31

customer[(*customerNumber)++] = n;
32

}
33

return 1;
34

}
35

int NotSame(int *number,const int count, int *m,int *stamp) //求不同一組郵票類(lèi)別的個(gè)數(shù)和郵票的最大面值。
36

{
37

int i,j, c,s;
38

c = 0;
39

*m = stamp[number[0]];
40

for(i = 0; i < count; i++)
41

{
42

if( *m < stamp[number[i]]) //求最大面值的郵票
43

*m = stamp[number[i]];
44

s = 0;
45

for(j = 0; j < i; j++) //求不同面值郵票的個(gè)數(shù)
46

{
47

if(number[i] == number [j])
48

{
49

s = 1;
50

break;
51

}
52

}
53

if(0 == s)
54

c++;
55

}
56

return c;
57

}
58

void Divide(int sum, int *number, int *stamp,int n, int *count, int same,int start)
61

{
62

int i;
63

int t;
64

if( *count > 4 )
65

return;
66

else if( sum == 0 && *count <= 4) //郵票個(gè)數(shù)《=4的時(shí)候且保存在數(shù)組number中的郵票面值=sum的時(shí)候。
67

{
68

same = NotSame(number, *count,&t, stamp);
69

if( same > reNumber || same == reNumber && reCount > *count || same == reNumber && reCount == *count && reMax < t )//根據(jù)不同的條件來(lái)判斷。
70

{
71

reMax = t;
72

reCount = *count;
73

reNumber = same;
74

for(i = 0; i < *count; i++)
75

result[i] = number[i];
76

tie = 0;
77

}
78

else if(same == reNumber && reCount == *count && reMax == t)//當(dāng)郵票面值的最大值、郵票種類(lèi)數(shù)，郵票個(gè)數(shù)相等時(shí)。
79

{
80

tie = 1;
81

}
82

return;
84

}
85

for(i = start; i < n; i++) //遞歸搜索
86

{
87

sum -= stamp[i];
88

if(sum >= 0)
89

{
90

number[(*count)++] = i;
91

Divide(sum, number, stamp, n, count,same,i);
92

(*count)--;
93

}
94

sum += stamp[i];
95

}
96

}
97

int main(int argc, char* argv[])
100

{
101

int stamp[100], customer[100]; //stamp保存郵票的面值，customer保存客戶(hù)需要郵票的總面值。
102

int number[5]; //臨時(shí)數(shù)據(jù)，記錄滿(mǎn)足條件的臨時(shí)結(jié)果。此前提交一直WA的原因是number分配的空間太小了！
103

int count,stampNumber = -1, customerNumber = -1;//stampNumber是郵票的個(gè)數(shù)，customerNumber是客戶(hù)個(gè)數(shù)
104

int i,j;
105

106

do
107

{
108

memset(stamp, 0, 100*sizeof(int));
109

memset(customer, 0, 100*sizeof(int));
110

memset(number, 0 ,4);
111

if(GetNumber(stamp, customer, &stampNumber, &customerNumber) == -1)
112

break;
113

for(i = 0; i < customerNumber; i++)
114

{
115

reMax = -1; //對(duì)數(shù)據(jù)初始化。
116

memset(result, 0, 4);
117

reNumber = -1;
118

count=0;
119

tie = 0;
120

Divide(customer[i], number,stamp, stampNumber/*+1*/,&count, -1,0);
121

if(reNumber != -1) //打印。
122

{
123

if(tie == 0) //找到滿(mǎn)足條件的結(jié)果。
124

{
125

printf("%d (%d):", customer[i], reNumber);
126

for(j = 0; j < reCount; j++)
127

printf(" %d",stamp[result[j]]);
128

printf("\n");
129

}
130

else if( tie == 1) //存在郵票面值的最大值、郵票種類(lèi)數(shù)，郵票個(gè)數(shù)相同的答案
131

{
132

printf("%d (%d): tie\n",customer[i], reNumber);
133

}
134

}
135

else //不滿(mǎn)足條件
136

{
137

printf("%d ---- none\n",customer[i]);
138

}
139

}
140

}while(1);
141

return 0;
142

}

posted on 2008-07-01 09:56 Leon916 閱讀(1944) 評(píng)論(4) 編輯收藏引用

評(píng)論:

# re: acm pku 1010 程序企業(yè)即時(shí)通訊 Posted @ 2008-07-01 12:43
哈哈，寫(xiě)的挺好的，加油哦。回復(fù) 更多評(píng)論
# re: acm pku 1010 程序[未登錄](méi) Leon Posted @ 2008-07-01 14:34
謝謝企業(yè)即時(shí)通訊，謝謝你的鼓勵(lì) 回復(fù) 更多評(píng)論
# re: acm pku 1010 程序水 Posted @ 2008-07-01 15:23
挺不錯(cuò)的，兄弟一直在做acm嗎？回復(fù) 更多評(píng)論
# re: acm pku 1010 程序 qingzheng Posted @ 2010-07-06 19:02
似乎沒(méi)有用到動(dòng)態(tài)規(guī)劃回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶(hù)登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理


Copyright © Leon916	Powered by: 博客園模板提供：滬江博客

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品