pat 1069 The Black Hole of Numbers
水题，代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std; bool isSame(char buf[])
{
int i = ;
while(buf[i] != '\0')
{
if(buf[i] != buf[])return false;
else i++;
}
return true;
} int main()
{
int num;
scanf("%d", &num);
char buf[];
sprintf(buf, "%04d", num);
if(isSame(buf))
{
printf("%04d - %04d = 0000", num, num);
return ;
}
int len = strlen(buf);
do
{
sort(buf, buf+len, greater<char>());
int decre = atoi(buf);
sort(buf, buf+len);
int incre = atoi(buf);
num = decre - incre;
sprintf(buf, "%04d", num);
printf("%04d - %04d = %04d\n", decre, incre, num);
}while(num != );
return ;
}
水题，按照单价贪心选择即可。注意的是题目中的月饼的存货量用double类型，用int第三个数据通不过。代码如下：
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std; struct UnitPrice
{
double val;
int index;
}; bool comp(UnitPrice a, UnitPrice b)
{
return a.val > b.val;
} int main()
{
//freopen("input.txt","r",stdin);
int N,D;
scanf("%d%d", &N, &D);
double *amount = new double[N];
double *price = new double[N];
UnitPrice *unitPrice = new UnitPrice[N];
for(int i = ; i < N; i++)
scanf("%lf", &amount[i]);
for(int i = ; i < N; i++)
{
scanf("%lf", &price[i]);
unitPrice[i].val = price[i] / amount[i];
unitPrice[i].index = i;
}
sort(&unitPrice[], &unitPrice[N], comp);
double profit = 0.0;
int j = ;
while(D > && j < N)
{
int k = unitPrice[j++].index;
if(D >= amount[k])
{
profit += price[k];
D -= amount[k];
}
else
{
profit += (D*1.0/amount[k])*price[k];
D = ;
}
}
printf("%.2f\n" ,profit);
return ;
}
水题，遍历字符串，统计每个单词出现次数即可。代码如下：
#include<iostream>
#include<string>
#include<map>
#include<algorithm>
using namespace std; bool isValid(char c)
{
if((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') ||
(c >= '' && c <= ''))
return true;
else return false;
} int main()
{
string buf, maxWord;
getline(cin, buf);
transform(buf.begin(),buf.end(),buf.begin(), ::tolower);
map<string,int> words;
int i = , times = ;
while( i < buf.length() )
{
while( i < buf.length() && isValid(buf[i]) == false) i++;
if(i < buf.length())
{
int start = i++;
while( i < buf.length() && isValid(buf[i]) == true) i++;
if( i <= buf.length())// 这里注意要<=,不能是<
{
string word = buf.substr(start, i-start);
if(words.find(word) == words.end())
{
words[word] = ;
if(times < ){times = ; maxWord = word;}
}
else
{
words[word] ++;
if(times < words[word] ||
(times == words[word] && word < maxWord))
{
times = words[word];
maxWord = word;
}
}
}
}
}
cout<<maxWord<<" "<<times;
return ;
}
题目的意思是选出一个加油站，求出加油站到几个house的距离的最小值，从这些最小值中选出一个最小的记为k(即距离station最近的的house)，选择的加油站要使k最大。理解题目意思后就很简单了，只要依次以每个候选加油站为起点计算单源最短路径，然后计算k，选择k最大的加油站即可。代码如下：
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<climits>
using namespace std;
const int INF = INT_MAX; int index(char buf[], int houseNum)
{
if(buf[] == 'G')
return atoi(buf+) + houseNum - ;
else
return atoi(buf) - ;
} //以src为起点的单源最短路径
void Dijkstra(int src, int dist[], int **graph, int n)
{
bool *used = new bool[n];
for(int i = ; i < n; i++)
{dist[i] = graph[src][i]; used[i] = false;}
for(int i = ; i < n; i++)
{
int tmin = INF,k;
for(int j = ; j < n; j++)
if(!used[j] && tmin > dist[j])
{
tmin = dist[j];
k = j;
}
used[k] = true;
for(int j = ; j < n; j++)
if(dist[k] != INF && graph[k][j] != INF &&
dist[k] + graph[k][j] < dist[j])
{
dist[j] = dist[k] + graph[k][j];
}
}
delete used;
}
int main()
{
//freopen("input.txt", "r", stdin);
int houseNum, stationNum,roadNum,range;
scanf("%d%d%d%d", &houseNum, &stationNum, &roadNum, &range);
const int nodeNum = houseNum + stationNum;
int **graph = new int*[nodeNum];
for(int i = ; i < nodeNum; i++)
{
graph[i] = new int[nodeNum];
for(int j = ; j < nodeNum; j++)
graph[i][j] = (i != j ? INF:);
}
for(int i = ; i < roadNum; i++)
{
char buf[];
scanf("%s", buf); int a = index(buf, houseNum);
scanf("%s", buf); int b = index(buf, houseNum);
scanf("%d", &graph[a][b]);
graph[b][a] = graph[a][b];
} double minDistance = -1.0, averageDistance = INF;
int Selectstation = -;
int dist[nodeNum];
for(int i = houseNum; i < nodeNum; i++)
{
Dijkstra(i, dist, graph, nodeNum);
double mindis = INF, averdis = 0.0;
bool flag = true;
for(int j = ; j < houseNum; j++)
{
if(dist[j] > range){flag = false; break;}
averdis += dist[j];
if(dist[j] < mindis)mindis = dist[j];
}
if(flag == false)continue;
averdis /= houseNum;
if(mindis > minDistance)
{
minDistance = mindis;
averageDistance = averdis;
Selectstation = i;
}
else if(mindis == minDistance)
{
if(averdis < averageDistance)
{
averageDistance = averdis;
Selectstation = i;
}
}
}
if(Selectstation != -)
printf("G%d\n%.1f %.1f\n", Selectstation+-houseNum, minDistance,
averageDistance);
else printf("No Solution\n");
return ;
}
【版权声明】转载请注明出处：http://www.cnblogs.com/TenosDoIt/p/3405252.html