1405. Mahershalalhashbaz, Nebuchadnezzar, and Billy Bob Benjamin Go to the RegionalsConstraints
Time Limit: 1 secs, Memory Limit: 32 MB
Description
The Association for Computing Machinery (ACM) is considering new rules for its regional programming contests, in part to solve some software problems. For instance, the program that prints out the badges for each team was designed so that the same font size is used to print all badges for that team. However, this means that if one member of the team has a very long name, then a very small font will be used to print all of the team’s badges, and this wouldn’t look very nice for someone with an extremely short name like "AL".
The initial solution proposed by the ACM was to put a limit on the length of contestants’ names. Someone pointed out that this would discriminate against teams from certain regions where bigger names are more common (for instance, children in the home towns of well-known actors are more likely to be named after that actor – imagine how many children in Oakland, California have been named after the actor Mahershalalhashbaz Ali since he became one of the stars of the television series The 4400).
As a compromise, the ACM decided to change the rule to require that "no team member’s name can have length more than two away from the average length of all the team member’s names." Using this rule, a team consisting of "MAHERSHALALHASHBAZ", "AL", and "BILL" would be disqualified (average name length is 8, so AL and BILL are not within 2). However, "MAHERSHALALHASHBAZ", "NEBUCHADNEZZAR", and "BILLYBOBBENJAMIN" would be okay (average name length is 16, and all team member names have length within 2 of this number). Given the names of n students, determine whether or not they can be placed into teams of k members each so that each team meets the requirements of the new ACM rule.
Input
Input will consist of multiple test cases. Each test case begins with a line consisting of two positive integersnandk, wheren≤ 1000,k≤ 8, andnis divisible byk. Following this arenlines, each containing a single name consisting only of upper case letters with no embedded, leading, or trailing blanks. These are the names of thenstudents who need to be organized into teams of sizekeach. No name will exceed 80 characters. The last test case is followed by a line containing two zeros.
Output
For each test case, output the case number (starting at 1) followed by either the word "yes" (meaning that it is possible to organize the students into teams of sizekso that no student on that team has a name whose length is greater than distance 2 from the average name lengths of the members on that team), or "no" if it is not possible. Use the format shown in the sample output. Insert a blank line between cases.
Sample Input3 3MAHERSHALALHASHBAZALBILL6 3MAHERSHALALHASHBAZALNEBUCHADNEZZARBILLBILLYBOBBENJAMINJILL0 0Sample OutputCase 1: noCase 2: yes
挺水的，按照字符串长短排序再比较就ok：0s
#include <stdio.h>#include <algorithm>#include <string.h>using namespace std;struct name {char a[85];};bool cmp(const name& aa, const name& bb) {return strlen(aa.a) < strlen(bb.a);}int main() {int control_case = 0, n, k;bool is_ok, control_blank = false;while (scanf("%d %d", &n, &k) && n && k) {scanf("\n");is_ok = true;name nn[n];for (int i = 0; i < n; i++) {gets(nn[i].a);}sort(nn, nn + n, cmp);/*for (int i = 0; i < n; i++) {printf("%s\n", nn[i].a);}*/int sum;for (int i = 0; i < n && is_ok; i += k) {sum = 0;for (int j = i; j < i + k; j++) {sum += (int)strlen(nn[j].a);}for (int j = i; j < i + k; j++) {if ((int)strlen(nn[j].a) > sum / k + 2) {is_ok = false;break;}}}if (control_blank)printf("\n");control_blank = true;control_case++;printf("Case %d: ", control_case);if (is_ok)printf("yes\n");elseprintf("no\n");}return 0;}
，没有伞的孩子必须努力奔跑！
