首页 > ACM题库 > HDU-杭电 > hdu 2409 Team Arrangement-模拟-[解题报告]C++
2014
01-26

hdu 2409 Team Arrangement-模拟-[解题报告]C++

Team Arrangement

问题描述 :

Barry Bennett, the coach of the Bings football team, wants to arrange his team for an important match against the Bangs. He decides on the formation he wants to play, for example 4-4-2, meaning that there will be four defenders, four midfielders, and two strikers (and of course, one goalkeeper). Your task is to determine the players who will play. For each available player, we know his role (e.g. midfielder). For each role, the players are selected in ascending order of their numbers. When the players are selected, you must determine the captain too, who is the player with the longest record in the team play. In case two players have the same record, the one with bigger number is chosen. Note that the captain is chosen among the players that are selected in the arrange.

输入:

The input consists of multiple test cases. The first 22 lines of each test case contain the data for the 22 available players in this format:

number name role year1�year’1 year2�year’2

number is the player number (unique positive integer less than 100). name is a string of at most 20 letters. role is a single character among G, D, M, S, for goalkeeper, defender, midfielder, and striker respectively. Each yeari �year’i pair (yeari ≤ year’i) shows the player has been a member of the team between the specified years (inclusive). The years are in four-digit format. There is at least one and at most 20 such pairs, and the same year is not repeated more than once in the list. There is a 23rd line describing the desired formation, like 4-4-2 in that format. Note that there are only three numbers in the formation (so, 4-3-2-1 is not valid), none of them is zero, and their sum is always 10. The input is terminated by a line containing a single 0.

输出:

The input consists of multiple test cases. The first 22 lines of each test case contain the data for the 22 available players in this format:

number name role year1�year’1 year2�year’2

number is the player number (unique positive integer less than 100). name is a string of at most 20 letters. role is a single character among G, D, M, S, for goalkeeper, defender, midfielder, and striker respectively. Each yeari �year’i pair (yeari ≤ year’i) shows the player has been a member of the team between the specified years (inclusive). The years are in four-digit format. There is at least one and at most 20 such pairs, and the same year is not repeated more than once in the list. There is a 23rd line describing the desired formation, like 4-4-2 in that format. Note that there are only three numbers in the formation (so, 4-3-2-1 is not valid), none of them is zero, and their sum is always 10. The input is terminated by a line containing a single 0.

样例输入:

9 PlayerA M 2000-2001 2003-2006
2 PlayerB M 2004-2006
10 PlayerC D 2001-2005
1 PlayerD D 2000-2001 2002-2004
11 PlayerE S 2003-2006
8 PlayerF M 2005-2006
22 PlayerG S 2005-2006
25 PlayerH G 2000-2001 2002-2003 2005-2006
6 PlayerI D 2003-2006
26 PlayerJ D 2003-2004 2000-2001
18 PlayerK M 2003-2004
19 PlayerL M 2000-2001 2003-2006
7 PlayerM S 2003-2006 1999-2001
21 PlayerN S 2003-2006
13 PlayerO S 2005-2006
15 PlayerP G 2001-2006
14 PlayerQ D 2003-2004
5 PlayerR S 2000-2005
20 PlayerS G 2000-2002 2003-2003
12 PlayerT M 2004-2005
3 PlayerU D 2000-2005
4 PlayerV M 2001-2004
4-4-2
0

样例输出:

7 PlayerM S
15 PlayerP G
1 PlayerD D
3 PlayerU D
6 PlayerI D
10 PlayerC D
2 PlayerB M
4 PlayerV M
8 PlayerF M
9 PlayerA M
5 PlayerR S

很简单,就是从22个球员中选出一支球队来:

1.按序号选出所有的球员,

2.选出最长时间的当队长。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;
struct P
{
    int num;
    char name[30];
    char ro[3];
    int year;
    bool operator<(const P t) const
    {
        return num<t.num;
    }
} re[25];
int a,b,c;

void out(int i)
{
    cout<<re[i].num<<" "<<re[i].name<<" "<<re[i].ro<<endl;//<<" "<<re[i].year<<endl;
}
bool solve()
{
    bool v[25];
    memset(v,false,sizeof(v));
    int g=-1,d[10],m[10],s[10];
    int ma=-1;
    for(int i=0; i<22; i++)
        if(!v[i]&&re[i].ro[0]=='G')
        {
            ma =1;
            g=i;
            break;
        }
    if(ma==-1) return false;
    v[g] = true;
    for(int j=0; j<a; j++)
    {
        ma=-1;
        for(int i=0; i<22; i++)
            if(!v[i]&&re[i].ro[0]=='D')
            {
                ma =1;
                d[j]=i;
                break;
            }
        if(ma==-1) return false;
        v[d[j]]=true;
    }
    for(int j=0; j<b; j++)
    {
        ma=-1;
        for(int i=0; i<22; i++)
            if(!v[i]&&re[i].ro[0]=='M')
            {
                ma =1;
                m[j]=i;
                break;
            }
        if(ma==-1) return false;
        v[m[j]]=true;
    }
    for(int j=0; j<c; j++)
    {
        ma=-1;
        for(int i=0; i<22; i++)
            if(!v[i]&&re[i].ro[0]=='S')
            {
                ma =1;
                s[j]=i;
                break;
            }
        if(ma==-1) return false;
        v[s[j]]=true;
    }
    int ans = 0;
    ma = -1;
    for(int i=0; i<22; i++)
        if(v[i]&&ma<=re[i].year)
        {
            ans = i;
            ma = re[i].year;
        }
    v[ans] = false;
    out(ans);
    if(v[g])
    out(g);
    for(int i=0; i<22; i++)
        if(v[i]&&re[i].ro[0]=='D')
            out(i);
    for(int i=0; i<22; i++)
        if(v[i]&&re[i].ro[0]=='M')
            out(i);
    for(int i=0; i<22; i++)
        if(v[i]&&re[i].ro[0]=='S')
            out(i);
    return true;
}
int main()
{
    freopen("in.txt","r",stdin);
    while(1)
    {
        int num,f,t,tim;
        char name[30],rol[5];
        char s;
        for(int i=0; i<22; i++)
        {
            scanf("%d",&num);
            if(num==0) goto tttt;
            scanf("%s",name);
            scanf("%s",rol);
            tim = 0;
            while(1)
            {
                scanf("%d-%d",&f,&t);
                tim+=(t-f+1);
                s = getchar();
                if(s=='\n') break;
            }
            re[i].num = num;
            strcpy(re[i].name,name);
            strcpy(re[i].ro,rol);
            re[i].year = tim;
        }
        sort(re,re+22);
        scanf("%d-%d-%d",&a,&b,&c);
        if(!solve())
            cout<<"IMPOSSIBLE TO ARRANGE"<<endl;
            cout<<endl;
    }
tttt:
    ;
    return 0;
}

解题转自:http://blog.csdn.net/binwin20/article/details/7833707


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  3. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  4. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

  5. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。