hdu1800_Fying_to_the_Mars

本文主要是介绍hdu1800_Fying_to_the_Mars，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一个士兵有一个数字表示他的级别，高级别的可以教低级别的。一个士兵最多有一个老师。没有老师是合法的。一个士兵也最多有一个学生。一个士兵可以没有老师或者没有学生。魔法棒是昂贵的，所以计算最少需要多少个魔法棒。每个士兵的级别数值可以达到30位因此要使用字符串来表示士兵的级别。此题使用贪心算法，计算最多的重复数。排序然后由前到后的遍历的方法会出现超时的问题。下面是超时的代码：

#include <iostream>  
#include <algorithm>
using namespace std;//找到相同数最多的
//所有的士兵
struct soldier_type{char level[32];
};
int ecount[3001];
struct soldier_type soldier[3001];/*void check_s(int N)
{for(int i=0;i<N;i++)printf("%s\n",soldier[i].level);
}*/
//小的在前
int cmp_str(char a[],char b[])
{int ha = 0;int hb = 0;int lena = strlen(a);int lenb = strlen(b);while(a[ha]=='0')ha++;while(b[hb]=='0')hb++;int clena = lena-ha;int clenb = lenb-hb;if(clena<clenb)return -1;     //小于为零 else if(clena>clenb)return 1;      //大于为一 else{while(ha<lena&&a[ha]==b[hb]){ha++;hb++;}if(ha<lena){if(a[ha]<b[hb])return -1;elsereturn 1;}else{return 0;}}
}
bool cmp_s(soldier_type sa,soldier_type sb)
{//首位去零char * a =sa.level;char * b =sb.level; int re = cmp_str(a,b);if(re==-1) return true;else return false;
}
int main()
{int N;// 0<=N<=3000while(scanf("%d",&N)!=EOF){for(int i=0;i<N;i++){scanf("%s",soldier[i].level);ecount[i]=1;}//check_s(N);//putchar(10);sort(soldier,soldier+N,cmp_s);//check_s(N);int max = 1;for(int i=0;i<N-1;i++){if(cmp_str(soldier[i].level,soldier[i+1].level)==0){ecount[i+1]+=ecount[i];                                                 if(max<ecount[i+1])max=ecount[i+1];}}printf("%d\n",max);}return 0;
}

网上粘了一个很简单的算法，但是在下认为这个代码是错误的，虽然可以通过oj，但是int类型并不能表示30位的整数，如果30位的整数在输入是不同的数转化为int类型的数时变为相同的数那么一定会出现错误。给大家参考。

#include <iostream>
#include <map>
using namespace std;
int main()
{int n;while(scanf("%d",&n)==1){int i;map<int,int> mp;int max=INT_MIN;for(i=0;i<n;i++){int level;scanf("%d",&level);mp[level]++;if(mp[level]>max){max=mp[level]; }}printf("%d\n",max);}return 0;
}

另一个从网上看到使用hash来解决此问题的，但是我还不明白为什么不会出现索引的冲突问题。给大家看看，如果知道原因请不吝赐教。

#include<stdio.h>
#include<string.h>
#define Max 70003
int hashlevel[Max];unsigned int BKDRHash(char * str)
{while(*str=='0')*str++;unsigned int seed=131;unsigned int hash=0;//从前缀非0，开始while(*str){hash=hash*seed + *str++;}return (hash&0x7FFFFFFF);
}int main()
{int N;while(scanf("%d",&N)!=EOF){char tempstr[30];unsigned int index;memset(hashlevel,0,sizeof(hashlevel));int maxlevel=0;for(int i=0;i<N;i++){scanf("%s",tempstr);index=BKDRHash(tempstr);hashlevel[index]++;if(hashlevel[index]>maxlevel)//免得待会又要遍历一次maxlevel=hashlevel[index];}printf("%d\n",maxlevel);}return 0;
}

这篇关于hdu1800_Fying_to_the_Mars的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---