发表于

1076 Wifi密码（15 point(s)）

下面是微博上流传的一张照片：“各位亲爱的同学们，鉴于大家有时需要使用 wifi，又怕耽误亲们的学习，现将 wifi 密码设置为下列数学题答案：A-1；B-2；C-3；D-4；请同学们自己作答，每两日一换。谢谢合作！！~”—— 老师们为了促进学生学习也是拼了…… 本题就要求你写程序把一系列题目的答案按照卷子上给出的对应关系翻译成 wifi 的密码。这里简单假设每道选择题都有 4 个选项，有且只有 1 个正确答案。

wifi.jpg

输入格式：

输入第一行给出一个正整数 N（≤ 100），随后 N 行，每行按照 编号-答案 的格式给出一道题的 4 个选项，T 表示正确选项，F 表示错误选项。选项间用空格分隔。

输出格式：

在一行中输出 wifi 密码。

输入样例：

8
A-T B-F C-F D-F
C-T B-F A-F D-F
A-F D-F C-F B-T
B-T A-F C-F D-F
B-F D-T A-F C-F
A-T C-F B-F D-F
D-T B-F C-F A-F
C-T A-F B-F D-F

输出样例：

13224143

Solution:

1, 将整行当作一个string来读
2, 用scanf读单个选项

#include <iostream>
#include <string>
using namespace std;
int main() {
  int N; cin >> N;
  getchar();
  while (N--) {
    string s;
    getline(cin, s);
    cout << s[s.find('T')-2]-'A' + 1;
  }
  cout << endl;
  return 0;
}
#include <cstdio>
char s[4];
int main() {
  int N;
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 4; j++) {
      scanf("%s", s);
      if (s[2] == 'T') {
        printf("%d", s[0] - 'A' + 1);
      }
    }
  }
  printf("\n");

  return 0;
}

发表于

1071 小赌怡情（15 point(s)）

常言道“小赌怡情”。这是一个很简单的小游戏：首先由计算机给出第一个整数；然后玩家下注赌第二个整数将会比第一个数大还是小；玩家下注 t 个筹码后，计算机给出第二个数。若玩家猜对了，则系统奖励玩家 t 个筹码；否则扣除玩家 t 个筹码。

注意：玩家下注的筹码数不能超过自己帐户上拥有的筹码数。当玩家输光了全部筹码后，游戏就结束。

输入格式：

输入在第一行给出 2 个正整数 T 和 K（≤ 100），分别是系统在初始状态下赠送给玩家的筹码数、以及需要处理的游戏次数。随后 K 行，每行对应一次游戏，顺序给出 4 个数字：

n1 b t n2
其中 n1 和 n2 是计算机先后给出的两个[0, 9]内的整数，保证两个数字不相等。b 为 0 表示玩家赌小，为 1 表示玩家赌大。t 表示玩家下注的筹码数，保证在整型范围内。

输出格式：

对每一次游戏，根据下列情况对应输出（其中 t 是玩家下注量，x 是玩家当前持有的筹码量）：

玩家赢，输出 Win t! Total = x.；
玩家输，输出 Lose t. Total = x.；
玩家下注超过持有的筹码量，输出 Not enough tokens. Total = x.；
玩家输光后，输出 Game Over. 并结束程序。

输入样例 1：

100 4
8 0 100 2
3 1 50 1
5 1 200 6
7 0 200 8

输出样例 1：

Win 100! Total = 200.
Lose 50. Total = 150.
Not enough tokens. Total = 150.
Not enough tokens. Total = 150.

输入样例 2：

100 4
8 0 100 2
3 1 200 1
5 1 200 6
7 0 200 8

输出样例 2：

Win 100! Total = 200.
Lose 200. Total = 0.
Game Over.

Solution:

输出的先后顺序, 首先要判断筹码是否足够；
接着判断是赢还是输, 赢没什么问题, 输了先打印剩余的Total, 根据Total来判断游戏是否结束。

坑点1: 对于输出格式比较有要求的, 用printf好控制
坑点2: 输了之后, 不用再判断是否剪完的total<0, 因为筹码不够早就continue, 只要判断total是否为0就行

#include <cstdio>
int main() {
  int total, T;
  scanf("%d %d", &total, &T);
  int n1, b, t, n2;
  while (T--) {
    scanf("%d %d %d %d", &n1, &b, &t, &n2);
    if (t > total) {
      printf("Not enough tokens.  Total = %d.\n", total);
      continue;
    }
    if ((n1 < n2 && b) || (n1 > n2 && !b)) {
      total += t;
      printf("Win %d!  Total = %d.\n", t, total);
    } else {
      total -= t;
      printf("Lose %d.  Total = %d.\n", t, total);
      if (!total) { printf("Game Over.\n"); break;}
    }
  }
  return 0;
}

发表于

1035 插入与归并（25 point(s)）

根据维基百科的定义：

插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

归并排序进行如下迭代操作：首先将原始序列看成 N 个只包含 1 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 1 个有序的序列。

现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？

输入格式：

输入在第一行给出正整数 N (≤100)；随后一行给出原始序列的 N 个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。

输出格式：

首先在第 1 行中输出Insertion Sort表示插入排序、或Merge Sort表示归并排序；然后在第 2 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。

输入样例 1：

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

输出样例 1：

Insertion Sort
1 2 3 5 7 8 9 4 6 0

输入样例 2：

10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6

输出样例 2：

Merge Sort
1 2 3 8 4 5 7 9 0 6

Solution:

观察插入排序和归并排序的数列特征。 插入排序索引i之前有序(注意这里的有序是指非降序, case4被狂坑), i之后与未排序的数列对应相同, 如果不满足上述条件的就是 归并排序。

判断出插入排序后, 可以直接根据已排序的索引i对原数列进行整体的排序; 但判断出归并排序后, 需要对整个排序过程进行模拟, 直到找到S与题中给出的T数列吻合, 再对S进行一次排序。

第一个坑点:
这样做case4, 6WA, 第一次自己实在不知道问题出在哪里,去看了看别人的代码,

发现对 归并排序的过程需要重新模拟 , 这点不是不是很理解。后来我想通了:

比如Sample2:

10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6

判断完有序i=2, 下一次step = 2*2 = 4, 完美！！！

但后面再看这个思路时, 真是被自己笑哭了。

10
1 2 3 4 7 5 9 4 0 6
1 2 3 4 5 7 4 9 0 6

如果是这个case, i = 4, 那么step = 4*2 = 8, 完美吗？ 明明也上一次排序的step也只是2..

因此需要对归并排序过程进行模拟,

坑点二
2, 对于每次排序, 只需要理解insert-sort和merge-sort的思想, 可以用std::sort来代替排序带的代码, 用下标进行管理。

坑点三
3, 对有序的判断应该是, T[i-1] <= T[i], 小小等号之差…case4 WA
回顾自己写成 T[i-1] < T[i] 已经好多次了, 现在总该长记性了。。

升序和非降序的区别

  • 升序, 数列符合 a[i+1] > a[i]
  • 非降序, 数列符合 a[i+1] >= a[i]

代码:

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 105;
int S[MAXN];
int T[MAXN];
int main() {
  int N;
  scanf("%d", &N);
  for (int i = 0; i < N; i++)  scanf("%d", &S[i]);
  for (int i = 0; i < N; i++)  scanf("%d", &T[i]);

  int i, j;
  for (i = 1; i < N && T[i-1] <= T[i]; i++) { }    // case4
  for (j = i; j < N && S[j] == T[j]; j++) { }
  if (j == N) {
    printf("Insertion Sort\n");
    sort(S, S+i+1);
  } else {
    printf("Merge Sort\n");
    int flag = 1;
    for (int step = 2; step/2 <= N && flag; step *= 2) {  // case6
      flag = 0;
      for (int k = 0; k < N; k++) if (S[k] != T[k]) { flag = 1; break;}

      for (i = 0; i < N; i += step) {
        sort(S+i, S + min(i+step, N));
      }
    }
  }

  for (int k = 0; k < N; k++) {
    if (k) printf(" ");
    printf("%d", S[k]);
  }
  printf("\n");

  return 0;
}

整个修改过程也贴上来, 方便大家查错。
1035 - 插入与归并.cpp)

发表于

1030 完美数列(25)（25 point(s)）

给定一个正整数数列，和正整数p，设这个数列中的最大值是M，最小值是m，如果M <= m * p，则称这个数列是完美数列。

现在给定参数p和一些正整数，请你从中选择尽可能多的数构成一个完美数列。

输入格式：

输入第一行给出两个正整数N和p，其中N（<= 10^5^）是输入的正整数的个数，p（<= 10^9^）是给定的参数。第二行给出N个正整数，每个数不超过10^9^。

输出格式：

在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。

输入样例：

10 8
2 3 20 4 5 1 6 7 8 9

输出样例：

8

Solution:

思路1: (只有case4超时的思路):
指针i从左往右移动, 指针j从右往左移动, 当j所指向的数M, if (a[j] > a[i] p) j–; 算出此时j-i+1就是数列大小, 保留最大的那个值; 更进一步加快这个算法的话, i移动过程中, 剩余的长度比max小的给跳过
思路2:
指针i从左往右移动, j从i+max开始(只找比当前长度还大的数列), 移动到满足 M <= mp的极值或最右, 也许要更新max的值.

思路2的j指针的移动, 是根据max动态变化的, 不用在内层循环中, 再去判断 M <= m*p这层关系来确定是不是要继续深入i.

坑点:
当心整数乘法溢出, 因为p<=10^9, 整数的范围在-2 10^9~ 2 10^9之间, 因此用long long, 可达9 * 10 ^ 18

#include <cstdio>
#include <algorithm>
const int MAXN = 100050;
long long a[MAXN];
int main() {
  int N, p;
  scanf("%d %d", &N, &p);
  for (int i = 0; i < N; i++) scanf("%lld", &a[i]);
  std::sort(a, a+N);

  int max = 0;
  for (int i = 0; i < N; i++) {
    int j = i+max;
    for ( ; j < N && a[j] <= a[i]*p; j++) { }
    int tmp = j-i;
    if (tmp > max) max = tmp;
  }
  printf("%d\n", max);
  return 0;
}

另外附上, 根据我自己的思路改进的两个版本:

#include <cstdio>
#include <algorithm>
const int MAXN = 100050;
long long a[MAXN];
int main() {
  int N, p;
  scanf("%d %d", &N, &p);
  for (int i = 0; i < N; i++) scanf("%lld", &a[i]);
  std::sort(a, a+N);
  
  int i = 0, j, max = 0;
  while (i < N) {
    j = N-1;
    while (a[i]*p < a[j] && i <= j) j--;
    int cnt = j-i+1;
    if (cnt > max) max = cnt;
    i++;
  }
  printf("%d\n", max);

  return 0;
}

{
  ...
  int i = 0, j, max = 0;
  while (i < N && (max < N-i)) {
    j = N-1;
    while (a[i]*p < a[j] && i <= j) j--;
    int cnt = j-i+1;
    if (cnt > max) max = cnt;
    i++;
  }
  printf("%d\n", max);
  ...
}

发表于

1025 PAT Ranking (25)（25 point(s)）

Programming Ability Test (PAT) is organized by the College of Computer Science and Technology of Zhejiang University. Each test is supposed to run simultaneously in several places, and the ranklists will be merged immediately after the test. Now it is your job to write a program to correctly merge all the ranklists and generate the final rank.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive number N (<=100), the number of test locations. Then N ranklists follow, each starts with a line containing a positive integer K (<=300), the number of testees, and then K lines containing the registration number (a 13-digit number) and the total score of each testee. All the numbers in a line are separated by a space.

Output Specification:

For each test case, first print in one line the total number of testees. Then print the final ranklist in the following format:

registration_number final_rank location_number local_rank

The locations are numbered from 1 to N. The output must be sorted in nondecreasing order of the final ranks. The testees with the same score must have the same rank, and the output must be sorted in nondecreasing order of their registration numbers.

Sample Input:

2
5
1234567890001 95
1234567890005 100
1234567890003 95
1234567890002 77
1234567890004 85
4
1234567890013 65
1234567890011 25
1234567890014 100
1234567890012 85
Sample Output:

9
1234567890005 1 1 1
1234567890014 1 2 1
1234567890001 3 1 2
1234567890003 3 1 2
1234567890004 5 1 4
1234567890012 5 2 2
1234567890002 7 1 5
1234567890013 8 2 3
1234567890011 9 2 4

Solution:

排序规则: 分数不同时, 分数高的在前; 分数相同时, 按照准考证号字典序排序

几个注意点:
1, 把一个考生的信息放进一个node, 跟我以前自己做时, 思路更清晰了。
2, 确定排名时, 分数不同不是简单的+1, 而是i+1, 即 1 2 2 4 5 5 5 8 ..
3, 字符串已经重载了所有的比较运算符, 可以直接用<比较
4, 在存储和输出排名时, 输出时, 边计算边打印

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

struct Testee {
  string id;
  int score;
  int final_rank;
  int local_number;
  int local_rank;
};

vector<Testee> v;

bool cmp_score(Testee t1, Testee t2) {
  if (t1.score != t2.score) {
    return t1.score > t2.score;
  } else {
    return t1.id < t2.id;
  }
}

int main() {
  int N;
  cin >> N;
  for (int in = 0; in < N; in++) {
    int K; cin >> K;
    vector<Testee> tmp_v;
    for (int i = 0; i < K; i++) {
      Testee node;
      string id_t; int score_t;
      cin >> id_t >> score_t;
      node.id = id_t; node.score = score_t; node.local_number = in+1;
      tmp_v.push_back(node);
    }
    sort(tmp_v.begin(), tmp_v.end(), cmp_score);
    int r = 1;
    for (int i = 0; i < K; i++) {
      if (i > 0 && tmp_v[i].score != tmp_v[i-1].score) {
        r = i+1;
      }
      tmp_v[i].local_rank = r;
      v.push_back(tmp_v[i]);
    }
  }
  sort(v.begin(), v.end(), cmp_score);

  cout << v.size() << endl;
  int r = 1;
  for (int i = 0; i < v.size(); i++) {
    if (i > 0 && v[i].score != v[i-1].score) {
      r = i+1;
    }
    cout << v[i].id << " " << r << " "
         << v[i].local_number << " " << v[i].local_rank << endl;
  }

  return 0;
}

作死, 去掉vector, string, iostream的代码, 用下标管理数组, 标准IO用cstdio
不过是一次很好的尝试…用num计数, 排序属于原地排序, 不占用额外的内存..
但也让我知道..真的刷题时, 别用数组作西..

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

struct Testee {
  char id[15];
  int score;
  int final_rank;
  int local_number;
  int local_rank;
} stu[100050];

bool cmp(Testee t1, Testee t2) {
  if (t1.score != t2.score) {
    return t1.score > t2.score;
  } else {
    return strcmp(t1.id, t2.id) < 0;
  }
}

int main() {
  int N, K, num = 0;
  scanf("%d", &N);
  for (int in = 0; in < N; in++) {
    scanf("%d", &K);
    for (int i = 0; i < K; i++) {
      scanf("%s %d", stu[num].id, &stu[num].score);
      stu[num].local_number = in+1;
      num++;
    }
    sort(stu+num-K, stu+num, cmp);
    int r = 1;
    stu[num-K].local_rank = 1;
    for (int i = num-K+1; i < num; i++) {
      if (stu[i].score == stu[i-1].score) {
        stu[i].local_rank = stu[i-1].local_rank;
      } else {
        stu[i].local_rank = i + 1 - (num-K);
      }
    }
  }
  sort(stu, stu+num, cmp);

  printf("%d\n", num);
  int r = 1;
  for (int i = 0; i < num; i++) {
    if (i > 0 && stu[i].score != stu[i-1].score) {
      r = i+1;
    }
    printf("%s %d %d %d\n", stu[i].id, r,
           stu[i].local_number, stu[i].local_rank);
  }
  return 0;
}

发表于

1055 集体照（25 point(s)）

拍集体照时队形很重要，这里对给定的 N 个人 K 排的队形设计排队规则如下：

每排人数为 N/K（向下取整），多出来的人全部站在最后一排；

后排所有人的个子都不比前排任何人矮；

每排中最高者站中间（中间位置为 m/2+1，其中 m 为该排人数，除法向下取整）；

每排其他人以中间人为轴，按身高非增序，先右后左交替入队站在中间人的两侧（例如5人身高为190、188、186、175、170，则队形为175、188、190、186、170。这里假设你面对拍照者，所以你的左边是中间人的右边）；

若多人身高相同，则按名字的字典序升序排列。这里保证无重名。

现给定一组拍照人，请编写程序输出他们的队形。

输入格式：

每个输入包含 1 个测试用例。每个测试用例第 1 行给出两个正整数 N（≤10^4总人数）和 K（≤10，总排数）。随后 N 行，每行给出一个人的名字（不包含空格、长度不超过 8 个英文字母）和身高（[30, 300] 区间内的整数）。

输出格式：

输出拍照的队形。即K排人名，其间以空格分隔，行末不得有多余空格。注意：假设你面对拍照者，后排的人输出在上方，前排输出在下方。

输入样例：

10 3
Tom 188
Mike 170
Eva 168
Tim 160
Joe 190
Ann 168
Bob 175
Nick 186
Amy 160
John 159

输出样例：

Bob Tom Joe Nick
Ann Mike Eva
Tim Amy John

Solution:

m/2-2  m/2-1  m/2  m/2+1  m/2+2

从最高位置开始, 偏移量(offset)为0, -1, +1, -2, +2, 核心问题就是构造这个数列,

int offset = ((j-1)/2+1)*flag;
flag *= 1;

不过这种做法, 我总觉得费时间, 应该有更好的做法.

坑点:
1, 题目中说身高相同按照名字的字典序排序, 如果是这样的话, Tim Amy John, Tim应该是排在应该是三人中的最高者, 但我把它改成降序后就正确了, 不知道是我理解有误, 还是它题目出错了.
2, 最后一行有多出来的人数, 在计算时用余数的方法把它加上.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct Node {
  char name[10];
  int h;
} a[10050];

Node ans[10050];

bool cmp(Node a, Node b) {
  if (a.h != b.h) return a.h < b.h;
  else return strcmp(a.name, b.name) > 0;  // why?
}


int main() {
  int N, K, m;
  scanf("%d %d", &N, &K);
  for (int i = 0; i < N; i++) {
    scanf("%s %d", a[i].name, &a[i].h);
  }
  int rst = N % K;

  sort(a, a+N, cmp);

  for (int i = K-1; i >= 0; i--) {
    int m = N/K, fp = i * m;
    if (i == K-1) m += rst;

    int j = 1, flag = -1;
    ans[m/2] = a[fp+m-1];
    while (j < m) {
      int offset = ((j-1)/2+1) * flag;
      ans[m/2+offset] = a[fp+m-1-j];
      flag *= -1;
      j++;
    }

    for (j = 0; j < m; j++) {
      if (j) printf(" ");
      printf("%s", ans[j].name);
    }
    printf("\n");
  }

  return 0;
}

发表于

1083 是否存在相等的差（20 point(s)）

给定 N 张卡片，正面分别写上 1、2、……、N，然后全部翻面，洗牌，在背面分别写上 1、2、……、N。将每张牌的正反两面数字相减（大减小），得到 N 个非负差值，其中是否存在相等的差？

输入格式：

输入第一行给出一个正整数 N（2 ≤ N ≤ 10 000），随后一行给出 1 到 N 的一个洗牌后的排列，第 i 个数表示正面写了 i 的那张卡片背面的数字。

输出格式：

按照“差值 重复次数”的格式从大到小输出重复的差值及其重复的次数，每行输出一个结果。

输入样例：

8
3 5 8 6 2 1 4 7

输出样例：

5 2
3 3
2 2

Solution

差值作为散列地址, f(key) = key, 在不同差值地址上计数, 对重复的差值进行排序

坑点:

  • 1, 牌从1开始计数, 1 2 3 4 5 ..
  • 2, 要对差值进行排序, 这里用了vector, 写cmp函数的方法, 不知道还有没有其他.
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 10000
typedef struct {
  int delta;
  int cnt;
} Node;

int cnt[MAXN];
vector<Node> ans;

int cmp(Node n1, Node n2) {
  return  n1.delta > n2.delta;
}

int main() {
  int N, v;
  cin >> N;
  memset(cnt, 0, sizeof(cnt));
  for (int i = 0; i < N; i++) {
    cin >> v;
    int d = (i < v) ? v-(i+1) : (i+1)-v;
    cnt[d]++;
  }

  for (int i = 0; i < MAXN; i++) {
    if (cnt[i] > 1) {
      Node node;
      node.delta = i; node.cnt = cnt[i];
      ans.push_back(node);
    }
  }

  sort(ans.begin(), ans.end(), cmp);
  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i].delta << " " << ans[i].cnt << endl;
  }
  return 0;
}

Solution2:

第二遍做, 找出其他方法.

既然开了一个散列, 可以记录一个max作为遍历的头, 从max向下遍历。

坑点:

重复是出现次数大于1

#include <cstdio>
#include <cstring>
int cnt[10050];

int main() {
  int N; scanf("%d", &N);
  memset(cnt, 0, sizeof(cnt));
  int max = 0, back = 0, rst = 0;
  for (int i = 0; i < N; i++) {
    scanf("%d", &back);
    rst = (back > i+1) ? back - (i+1) : i+1 - back;
    cnt[rst]++;
    max = rst > max ? rst : max;
  }
  
  for (int i = max; i >= 0; i--) {
    if (cnt[i] > 1) {
      printf("%d %d\n", i, cnt[i]);
    }
  }
  return 0;
}

发表于

1047 编程团体赛（20 point(s)）

编程团体赛的规则为：每个参赛队由若干队员组成；所有队员独立比赛；参赛队的成绩为所有队员的成绩和；成绩最高的队获胜。

现给定所有队员的比赛成绩，请你编写程序找出冠军队。

输入格式：

输入第一行给出一个正整数 N（≤10^4），即所有参赛队员总数。随后 N 行，每行给出一位队员的成绩，格式为：队伍编号-队员编号 成绩，其中队伍编号为 1 到 1000 的正整数，队员编号为 1 到 10 的正整数，成绩为 0 到 100 的整数。

输出格式：

在一行中输出冠军队的编号和总成绩，其间以一个空格分隔。注意：题目保证冠军队是唯一的。

输入样例：

6
3-10 99
11-5 87
102-1 0
102-3 100
11-9 89
3-2 61

输出样例：

11 176

Solution:

team作为address地址, f(key) = key; 对字符串根据分隔符求子串

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

int scores[1000];

int main() {
  int N; string s;
  cin >> N;
  memset(scores, 0, sizeof(scores));
  getchar();
  int max = 0;
  while (N--) {
    getline(cin, s);
    string team = s.substr(0, s.find("-"));
    string score = s.substr(s.find(" ")+1, s.length());
    int i_team = stoi(team);
    scores[i_team] += stoi(score);
    if (scores[i_team] > scores[max]) max = i_team;
  }
  cout << max << " " << scores[max] << endl;
  return 0;
}

发表于

1043 输出PATest（20 point(s)）

给定一个长度不超过 10^4的、仅由英文字母构成的字符串。请将字符重新调整顺序，按 PATestPATest…. 这样的顺序输出，并忽略其它字符。当然，六种字符的个数不一定是一样多的，若某种字符已经输出完，则余下的字符仍按 PATest 的顺序打印，直到所有字符都被输出。

输入格式：

输入在一行中给出一个长度不超过 10^4​的、仅由英文字母构成的非空字符串。

输出格式：

在一行中按题目要求输出排序后的字符串。题目保证输出非空。

输入样例：

redlesPayBestPATTopTeePHPereatitAPPT

输出样例：

PATestPATestPTetPTePePee

Solution:

Hash散列将字符key转化成对应索引, 每出现一次cnt+1, 让散列表中的字符按照顺序循环打印, 每次打印都减少次数, 直到次数为空

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

char chars[6] = {'P', 'A', 'T', 'e', 's', 't'};

int main() {
  int cnt[6];
  memset(cnt, 0, sizeof(cnt));
  string s; cin >> s;
  for (int i = 0; i < s.length(); i++) {
    for (int j = 0; j < 6; j++)
      if (s[i] == chars[j]) { cnt[j]++; break; }
    /*
    if (s[i] == 'P') cnt[0]++;
    else if (s[i] == 'A') cnt[1]++;
    else if (s[i] == 'T') cnt[2]++;
    else if (s[i] == 'e') cnt[3]++;
    else if (s[i] == 's') cnt[4]++;
    else if (s[i] == 't') cnt[5]++;
    */
  }
  
  int ok;
  do {
    ok = 0;
    for (int i = 0; i < 6; i++) {
      if (cnt[i]) {
        ok = 1;
        printf("%c", chars[i]);
        cnt[i]--;
      }
    }
  } while (ok);
  
  return 0;
}

发表于

1042 字符统计（20）（20 point(s)）

请编写程序，找出一段给定文字中出现最频繁的那个英文字母。

输入格式：

输入在一行中给出一个长度不超过 1000 的字符串。字符串由 ASCII 码表中任意可见字符及空格组成，至少包含 1 个英文字母，以回车结束（回车不算在内）。

输出格式：

在一行中输出出现频率最高的那个英文字母及其出现次数，其间以空格分隔。如果有并列，则输出按字母序最小的那个字母。统计时不区分大小写，输出小写字母。

输入样例：

This is a simple TEST. There ARE numbers and other symbols 1&2&3………..

输出样例：

e 7

Solution:

将字符的ascii码作为address, address = key, a[adrr] = cnt(key);
用max_p记录出现次数最多字符的ascii码, 打印时, 可以直接转换和索引.

坑点, case 2, 如果有并列, 输出字典序小的, 判断两个位置最大值是否相等, 且当前i对应字母更小;

另外我测试了ascii码的分布情况, 所以, 散列表大小开到150左右就ok了

'a' = 97, 'z' = 122, 'A' = 65, 'Z' = 90
'0' = 48, '9' = 57

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int cnt[200];   // 假设ascii200位
int main() {
  memset(cnt, 0, sizeof(cnt));
  string s;
  getline(cin, s);
  int max_p = 0;
  for (int i = 0; i < s.length(); i++) {
    if (isalpha(s[i])) {
      int ch = tolower(s[i]);
      cnt[ch]++;
      if (cnt[ch] > cnt[max_p]) max_p = ch;
      if (cnt[ch] == cnt[max_p] && (ch < max_p)) max_p = ch;
    }
  }
  printf("%c %d\n", max_p, cnt[max_p]);

  return 0;
}