c语言游戏分组问题,问题 B: 分组统计

分组统计

问题 B: 分组统计时间限制: 1 Sec 内存限制: 32 MB

提交: 416 解决: 107

[提交][状态][讨论版][命题人:外部导入]

题目描述

先输入一组数，然后输入其分组，按照分组统计出现次数并输出，参见样例。

输入

输入第一行表示样例数m，对于每个样例，第一行为数的个数n，接下来两行分别有n个数，第一行有n个数，第二行的n个数分别对应上一行每个数的分组，n不超过100。

输出

输出m行，格式参见样例，按从小到大排。

样例输入

1

7

3 2 3 8 8 2 3

1 2 3 2 1 3 1

样例输出

1={2=0,3=2,8=1}

2={2=1,3=0,8=1}

3={2=1,3=1,8=0}

思考

这个是典型的哈希算法了。

这个样例是统计每组数字里面各数字(出现在第一行的数字，这一次是3,2,8)的个数。

所以每一组数字要个数组3，记录2,3,8的个数

先搞一个在n个数字第一次出现时的数组num，记录那些数字出现了，出现了几次，以该数字为下标的数组值++，那这个数组大小应该是很大的啊 。

再来就是分组了，再来一个数组zu,以上一行出现过数字为下标，值为所分的组。

n不超过100。怎么表示这种性质呢？结构体？一个整型，记录其在第一行的n个数里的出现次数，再来一个数组，记录自己在不同组的出现次数。

组数肯定要小于n

本地实现

这问题几个月之前就遇到过了。

#include

#include

#include

//#include

#define maxn 10005

int cmp(const void*a, const void*b){

return *(int*)a - *(int*)b;//升序

}

int main(){

int m;

while(scanf("%d", &m) != EOF){

while(m--){

int n;

scanf("%d", &n);

int cishu[maxn][n+1]= {0};

//int temp[n+1] = INT_MAX;

int temp[n+1] = {0};

for(int i = 1; i <= n; i++){

scanf("%d", &temp[i]);

cishu[temp[i]][0]++;//将第一行数读入数组temp，并且在相应行第0列记录出现在第一行出现次数

}

int zu[n+1] = {0}, num = 0, kzu[n+1] = {0};

for(int i = 1; i <= n; i++) {

scanf("%d",&zu[i]);

kzu[zu[i]]++;

cishu[temp[i]][zu[i]]++;

}

/*二维数组里行代表这个数，列代表该行对应数在某组里出现的次数*/

for(int i = 1; i <= n; i++) {

if(kzu[i] > 0)

num++;

}

//num记录分的组的个数

/*该对第一行的n个数按大小排序了*/

qsort(temp+1, n, sizeof(temp[0]), cmp);

/*for(int i = 1; i <= n; i++){

printf("%dn", temp[i]);

}//排序正确*/

/*剔除重复项，建立新数组*/

int newtemp[n+1], newxu = 2;

newtemp[1] = temp[1];

for(int i = 2; i <= n; i++) {

if(temp[i] != temp[i-1])//if语句的括号后面跟分号，编译器竟然没error

newtemp[newxu++] = temp[i];

}

/*for(int i = 1; i < newxu; i++){

printf("%dn", newtemp[i]);

}//剔除重复项，新数组正确*/

for(int j = 1; j <= num; j++) {

printf("%d={", j); //第j组

for(int i = 1; i < newxu; i++){

printf("%d=%d", newtemp[i], cishu[newtemp[i]][j]);

if(i < newxu-1)

printf(",");

}

printf("}n");

}

}

}

return 0;

}

别人的代码1-二维数组

#include

#include

#include

using namespace std;

const int MaxN = 102;

int main()

{

#ifdef _DEBUG

ifstream cin("data.txt");

#endif // _DEBUG

//利用链表散列进行统计，这里用二维数组模拟

int m, n;

while (cin >> m)

{

while (m--)

{

int Table[MaxN][MaxN] = {0}, classFlag[MaxN] = {false}, Class[MaxN], ClaN = 0, Num[MaxN], tmp, NumUi[MaxN], N = 0;

cin >> n;

for (int i = 0; i < n; ++i)

cin >> Num[i];//读入第一行所有数

for (int i = 0; i < n; ++i)

{

cin >> tmp;

if (!classFlag[tmp])

{

classFlag[tmp] = true;

Class[ClaN++] = tmp;//该组的序号第一次出现时，记录进来

}

Table[tmp][Table[tmp][MaxN - 1]++] = Num[i];//建立这个表，第几组就是第几行 ，避免了数组越界

}//该数是第几组存进第几行的，存进哪一列呢？从第1列，开始存，该行最后一列记录了该组的数字个数

sort(Class, Class + ClaN);//组序号排序 ，ClaN记录组的个数

sort(Num, Num + n);//第一行数字排序

/*剔除重复项，建立新数组*/

for (int i = 0; i < n; ++i)

{

if (N == 0 || Num[i] != NumUi[N-1])

{

NumUi[N++] = Num[i];

}

}

for (int k = 0; k < ClaN; ++k)

{

printf("%d={", Class[k]);/*组号*/

for (int h = 0; h < N; ++h)/*按第一行数字顺序*/

{ /*查询，如果出现相同的，则数字加1*/

int c = 0, j = 0;

for (; j < Table[Class[k]][MaxN - 1]; ++j)

{

if (Table[Class[k]][j] == NumUi[h])

++c;

}

printf("%d=%d", NumUi[h], c);

if (h < N-1)

printf(",");

}

printf("}n");

}

}

}

#ifdef _DEBUG

cin.close();

system("pause");

#endif // _DEBUG

return 0;

}

别人的代码2-散列

#include

#include //max_element,unique_copy

#include

#include

using namespace std;

int main() {

int M;

while(cin>>M) {

while (M--) {

int N; //输入数据的个数

cin >> N;

int nums[N], cls[N]; //数据和类别

for (int i = 0; i < N; i++)

cin >> nums[i];

for (int i = 0; i < N; i++)

cin >> cls[i];

// 数据的最大值和类别

int max_cls = *max_element(cls, cls + N);

int max_num = *max_element(nums, nums + N);

// hash二维数组计数

int hashTable[max_cls + 1][max_num + 1];

// 全０初始化

memset(hashTable, 0, sizeof(hashTable));

for (int i = 0; i < N; i++)

hashTable[cls[i]][nums[i]]++;

//类排序去重

vector v2;

sort(cls, cls+N);

unique_copy(cls, cls + N, back_inserter(v2));

//nums排序去重

vector v;

sort(nums, nums + N);

unique_copy(nums, nums + N, back_inserter(v));

for (int i = 0; i < v2.size(); i++) {

cout << v2[i] << "={";

for (int j = 0; j < v.size(); j++) {

cout << v[j] << ‘=‘ << hashTable[v2[i]][v[j]];

if (j < v.size() - 1) cout << ‘,‘;

}

cout << ‘}‘ << endl;

}

}

}

return 0;

}

这里比较重要的是，取得容器内最大值，防止二维数组越界问题。

防止越界的散列

C++ STL之min_element()与max_element()(取容器中的最大最小值) - Angel_Kitty - 博客园 https://www.cnblogs.com/ECJTUACM-873284962/p/6734225.html

#include

#include

using namespace std;

bool cmp(int a,int b)

{

return a

// return a>b;

}

int main()

{

int num[]={2,3,1,6,4,5};

cout<

cout<

cout<b;改降序

cout<

return 0;

}

关于c语言初始化的问题

也就是说，要置零，使用memset最好了。

memset(cur,0,sizeof(cur))

AC代码

#include

#include //max_element,unique_copy

#include

#include

using namespace std;

int main() {

int M;

while(cin>>M) {

while (M--) {

int N; //输入数据的个数

cin >> N;

int nums[N], cls[N]; //数据和类别

for (int i = 0; i < N; i++)

cin >> nums[i];

for (int i = 0; i < N; i++)

cin >> cls[i];

// 数据的最大值和类别

int max_cls = *max_element(cls, cls + N);

int max_num = *max_element(nums, nums + N);

// hash二维数组计数

int hashTable[max_cls + 1][max_num + 1];

// 全０初始化

memset(hashTable, 0, sizeof(hashTable));

for (int i = 0; i < N; i++)

hashTable[cls[i]][nums[i]]++;

//类排序去重

vector v2;

sort(cls, cls+N);

unique_copy(cls, cls + N, back_inserter(v2));

//nums排序去重

vector v;

sort(nums, nums + N);

unique_copy(nums, nums + N, back_inserter(v));

for (int i = 0; i < v2.size(); i++) {

cout << v2[i] << "={";

for (int j = 0; j < v.size(); j++) {

cout << v[j] << ‘=‘ << hashTable[v2[i]][v[j]];

if (j < v.size() - 1) cout << ‘,‘;

}

cout << ‘}‘ << endl;

}

}

}

return 0;

}