PAT 1069 1070 1071 1072

水题，代码如下：

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 bool isSame(char buf[])
 8 {
 9     int i = 1;
10     while(buf[i] != '')
11     {
12         if(buf[i] != buf[0])return false;
13         else i++;
14     }
15     return true;
16 }
17 
18 int main()
19 {
20     int num;
21     scanf("%d", &num);
22     char buf[6];
23     sprintf(buf, "%04d", num);
24     if(isSame(buf))
25     {
26         printf("%04d - %04d = 0000", num, num);
27         return 0;
28     }
29     int len = strlen(buf);
30     do
31     {
32         sort(buf, buf+len, greater<char>());
33         int decre = atoi(buf);
34         sort(buf, buf+len);
35         int incre = atoi(buf);
36         num = decre - incre;
37         sprintf(buf, "%04d", num);
38         printf("%04d - %04d = %04d
", decre, incre, num);
39     }while(num != 6174);
40     return 0;
41 }

View Code

pat 1070 Mooncake

水题，按照单价贪心选择即可。注意的是题目中的月饼的存货量用double类型，用int第三个数据通不过。代码如下：

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 struct UnitPrice
 7 {
 8     double val;
 9     int index;
10 };
11 
12 bool comp(UnitPrice a, UnitPrice b)
13 {
14     return a.val > b.val;
15 }
16 
17 int main()
18 {
19     //freopen("input.txt","r",stdin);
20     int N,D;
21     scanf("%d%d", &N, &D);
22     double *amount = new double[N];
23     double *price = new double[N];
24     UnitPrice *unitPrice = new UnitPrice[N];
25     for(int i = 0; i < N; i++)
26         scanf("%lf", &amount[i]);
27     for(int i = 0; i < N; i++)
28     {
29         scanf("%lf", &price[i]);
30         unitPrice[i].val = price[i] / amount[i];
31         unitPrice[i].index = i;
32     }
33     sort(&unitPrice[0], &unitPrice[N], comp);
34     double profit = 0.0;
35     int j = 0;
36     while(D > 0 && j < N)
37     {
38         int k = unitPrice[j++].index;
39         if(D >= amount[k])
40         {
41             profit += price[k];
42             D -= amount[k];
43         }
44         else
45         {
46             profit += (D*1.0/amount[k])*price[k];
47             D = 0;
48         }
49     }
50     printf("%.2f
" ,profit);
51     return 0;
52 }

View Code

pat 1071 Speech Patterns 本文地址

水题，遍历字符串，统计每个单词出现次数即可。代码如下：

 1 #include<iostream>
 2 #include<string>
 3 #include<map>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 bool isValid(char c)
 8 {
 9     if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') ||
10        (c >= '0' && c <= '9'))
11         return true;
12     else return false;
13 }
14 
15 int main()
16 {
17     string buf, maxWord;
18     getline(cin, buf);
19     transform(buf.begin(),buf.end(),buf.begin(), ::tolower);
20     map<string,int> words;
21     int i = 0, times = 0;
22     while( i < buf.length() )
23     {
24         while( i < buf.length() && isValid(buf[i]) == false) i++;
25         if(i < buf.length())
26         {
27             int start = i++;
28             while( i < buf.length() && isValid(buf[i]) == true) i++;
29             if( i <= buf.length())// 这里注意要<=,不能是<
30             {
31                 string word = buf.substr(start, i-start);
32                 if(words.find(word) == words.end())
33                 {
34                     words[word] = 1;
35                     if(times < 1){times = 1; maxWord = word;}
36                 }
37                 else
38                 {
39                     words[word] ++;
40                     if(times < words[word] ||
41                        (times == words[word] && word < maxWord))
42                     {
43                         times = words[word];
44                         maxWord = word;
45                     }
46                 }
47             }
48         }
49     }
50     cout<<maxWord<<" "<<times;
51     return 0;
52 }

View Code

pat 1072 Gas Station 本文地址

题目的意思是选出一个加油站，求出加油站到几个house的距离的最小值，从这些最小值中选出一个最小的记为k(即距离station最近的的house)，选择的加油站要使k最大。理解题目意思后就很简单了，只要依次以每个候选加油站为起点计算单源最短路径，然后计算k，选择k最大的加油站即可。代码如下：

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<algorithm>
 4 #include<climits>
 5 using namespace std;
 6 const int INF = INT_MAX;
 7 
 8 int index(char buf[], int houseNum)
 9 {
10     if(buf[0] == 'G')
11         return atoi(buf+1) + houseNum - 1;
12     else
13         return atoi(buf) - 1;
14 }
15 
16 //以src为起点的单源最短路径
17 void Dijkstra(int src, int dist[], int **graph, int n)
18 {
19     bool *used = new bool[n];
20     for(int i = 0; i < n; i++)
21         {dist[i] = graph[src][i]; used[i] = false;}
22     for(int i = 1; i < n; i++)
23     {
24         int tmin = INF,k;
25         for(int j = 0; j < n; j++)
26             if(!used[j] && tmin > dist[j])
27             {
28                 tmin = dist[j];
29                 k = j;
30             }
31         used[k] = true;
32         for(int j = 0; j < n; j++)
33             if(dist[k] != INF && graph[k][j] != INF &&
34                dist[k] + graph[k][j] < dist[j])
35             {
36                 dist[j] = dist[k] + graph[k][j];
37             }
38     }
39     delete used;
40 }
41 int main()
42 {
43     //freopen("input.txt", "r", stdin);
44     int houseNum, stationNum,roadNum,range;
45     scanf("%d%d%d%d", &houseNum, &stationNum, &roadNum, &range);
46     const int nodeNum = houseNum + stationNum;
47     int **graph = new int*[nodeNum];
48     for(int i = 0; i < nodeNum; i++)
49     {
50         graph[i] = new int[nodeNum];
51         for(int j = 0; j < nodeNum; j++)
52             graph[i][j] = (i != j ? INF:0);
53     }
54     for(int i = 0; i < roadNum; i++)
55     {
56         char buf[10];
57         scanf("%s", buf); int a = index(buf, houseNum);
58         scanf("%s", buf); int b = index(buf, houseNum);
59         scanf("%d", &graph[a][b]);
60         graph[b][a] = graph[a][b];
61     }
62 
63     double minDistance = -1.0, averageDistance = INF;
64     int Selectstation = -1;
65     int dist[nodeNum];
66     for(int i = houseNum; i < nodeNum; i++)
67     {
68         Dijkstra(i, dist, graph, nodeNum);
69         double mindis = INF, averdis = 0.0;
70         bool flag = true;
71         for(int j = 0; j < houseNum; j++)
72         {
73             if(dist[j] > range){flag = false; break;}
74             averdis += dist[j];
75             if(dist[j] < mindis)mindis = dist[j];
76         }
77         if(flag == false)continue;
78         averdis /= houseNum;
79         if(mindis > minDistance)
80         {
81             minDistance = mindis;
82             averageDistance = averdis;
83             Selectstation = i;
84         }
85         else if(mindis == minDistance)
86         {
87             if(averdis < averageDistance)
88             {
89                 averageDistance = averdis;
90                 Selectstation  = i;
91             }
92         }
93     }
94     if(Selectstation != -1)
95         printf("G%d
%.1f %.1f
", Selectstation+1-houseNum, minDistance,
96                 averageDistance);
97     else printf("No Solution
");
98     return 0;
99 }

View Code