Main » 2011 » November » 10 » 韩国明星（解题报告+原程）
11:10 AM 韩国明星（解题报告+原程） | |
【问题描述】题解： 本题属于字符串处理题，如果用单纯的模拟是绝对超时的，因为有100000组数据，呵呵，转念一想，也就是查找给的那个人是费时间，所以我采取了二分查找的方法，速度一流，呵呵，上代码！！ 原程：C++语言: Codee#23888
#include #include #include #include using namespace std; int n,m; int find(); char str[100]; int cmp1(const void*a,const void *b); int cmp2(const void *a,const void *b); struct hehe { int mark; char s[100]; }q[100001]; int main() { freopen ("star.in","r",stdin); freopen ("star.out","w",stdout); scanf("%d\n",&n); for (int i=0;i<n;i++) { scanf("%[^'\n]\n",&q[i].s); q[i].mark=0; } qsort(q,n,sizeof(q[0]),cmp1); scanf("%d\n",&m); for (int i=0;i<m;i++) { scanf("%[^\n]\n",&str); int temp; temp=find(); int tmp; scanf("%d\n",&tmp); q[temp].mark+=tmp; } qsort(q,n,sizeof(q[0]),cmp2); for (int i=0;i<n;i++) { cout<<q[i].s<<endl<<q[i].mark<<endl; } return 0; } int cmp1(const void*a,const void *b) { struct hehe*c=(struct hehe*)a; struct hehe*d=(struct hehe*)b; return strcmp(c->s,d->s); } int find() { int l=0; int r,mid; r=n -1; mid=((l+r)>>1); while (l<r) { if (l==r) return l; else { if (strcmp(q[mid].s,str)<0) { l=mid+1; mid=((l+r)>>1); continue; } if (strcmp(q[mid].s,str)==0) { return mid; } if (strcmp(q[mid].s,str)>0) { r=mid-1; mid=((l+r)>>1); continue; } } } return l; } int cmp2(const void *a,const void *b) { struct hehe *c=(struct hehe*)a; struct hehe *d=(struct hehe*)b; return d->mark - c->mark; } | |
|
| |
| Total comments: 0 | |