百度之星2007初赛第一条-水果开会时段

百度之星2007年初赛第一条

时间好紧张,只完成了一题...................
由于这里ｂｌｏｇ的ｂｕｇ我把＜和＞替换为了全角

思路

用vector<vector<string>>来保存水果,相同的水果为一组

每个新水果都检查是否可以分到其中一组中,如果不行,新建一组

最后统计一下有多少组即可

时间紧张,代码写的有点混乱:)


1.水果开会时段

每个百度工程师团队都有一笔还算丰裕的食品经费，足够每天购置多种水果。水果往往下午送达公司前台。前台的姐姐们只要看到同时出现五种或以上的水果，就称之为“水果开会”。

从搜索引擎切词的语法角度，只要两种水果的名字中有一个字相同就属于同样的类别。例如“小雪梨”和“大雪梨”是同一种水果，而“核桃”和“水蜜桃”也被认为是同一种水果。尤其要指出的是，如果有三种水果x, y, z同时在前台出现，且x和y是同一种水果，y和z也是同一种水果的时候，x和z在此时也被认为是同一种水果（即使x和z并不包含相同的字）。现在前台的姐姐们想知道，今天是否有“水果开会”——五种或更多的水果同时在前台出现。

输入格式
输入的第一行只有一个整数n，表示购置水果的组数。接下来的n行表示水果的到达时间、取走时间（时间用1200到1900之间的正整数表示，保证取走时间大于到达时间）。剩下的字符串以空格分割每一种水果。如“1400 1600 雪梨水蜜桃”，表示下午两点到四点（包含两点和四点这两个时间点），雪梨和水蜜桃会在前台等待开会。每种水果名称由不超过十个汉字组成。

输出格式
输出仅一行，包含一个字符串Yes或No，分别表示今天水果开会与否。

输入样例1 例
3
1200 1400 雪梨 柠檬
1300 1400 西瓜 苹果
1400 1800 花生 水蜜桃

输出样例1 例
Yes

输入样例2 例
3
1200 1400 雪梨 柠檬
1400 1500 哦 大梨 呀
1500 1800 咦 大梨

输出样例2 例
No

样例解释
在样例1中，时刻1400有六种水果在前台；在样例2中，由于雪梨和大梨在任何时刻都是同一种水果，最多只有四种水果同时在前台。

评分规则
程序将运行在一台Linux机器上（内存使用不作严格限制），在每一测试用例上运行不能超过1秒，否则该用例不得分；
要求程序能按照输入样例的格式读取数据，按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据，该题将不得分；
该题共有10个测试数据集，每组数据均满足n＜=10，每个时段最多有10个水果，一共不超过50个水果；
该题目20分。

#include ＜fstream＞
#include ＜sstream＞
#include ＜iostream＞

#include ＜vector＞
#include ＜map＞
#include ＜list＞

#include ＜string＞

#include ＜algorithm＞
#include ＜functional＞

using namespace std;

#define BEG_END(c)        (c.begin()),(c.end())

typedef string::size_type str_size;

bool same(string a,string b)
{
    int len=b.size();
    for (int i=0;i!=len;i+=2)
    {
        if (a.find(b.substr(i,2)) != string::npos)return true;
    }
    return false;
}


template＜class T＞
bool right(T a,T b)
{
    vector＜vector＜string＞ ＞ total;
    for (;a!=b;++a)
    {int k=0;
    //    cout＜＜" size "＜＜(a-＞second).size()＜＜" ";
        next:
        while (k!=(a-＞second).size())
        {
           
            for (int i=0;i!=total.size();++i)
            {

                for (int j=0;j!=total[i].size();++j)
                {
                    if (same((a-＞second).at(k),total[i][j]))
                    {
                        total[i].push_back((a-＞second).at(k));
                        ++k;
                        goto next;
                    }
                }
            }
                            vector＜string＞ b;
                b.push_back((a-＞second).at(k));
                total.push_back(b);
            ++k;
        }
    }
    return total.size()＞4;
}

int main()
{
    int t;
    string line;
    int in,out;
    cin＞＞t;
    getline(cin,line);
    typedef  vector＜pair＜pair＜int,int＞,vector＜string＞ ＞ ＞ viis;
    vector＜pair＜pair＜int,int＞,vector＜string＞ ＞ ＞ all;
    while (t--)
    {
        getline(cin,line);
        istringstream ss(line);

        ss＞＞in＞＞out;
        string item;
        vector＜string＞ fruit;

        while (ss＞＞item)
        {
            fruit.push_back(item);
        }

        all.push_back(make_pair(make_pair(in,out),fruit));
        viis::iterator j=all.begin();
        for(viis::iterator i=all.begin();i!=all.end();++i){
            while((j-＞first).second＜(i-＞first).first){
                ++j;
            }
            if(right(j,i+1))
            {
                cout＜＜"Yes\n";
                goto END;
            }
        }
    }
        cout＜＜"No\n";
END:
    return 0;
}

/*
template＜class T＞
int all(T t){
    int total=0;
    int size=t.size();
    for(int i=0;i!=size;++i){
        total+=t[i].size();
    }
    return total;
}*/

评论

1 楼 sunnycare 2007-05-27  

说说思路吧，感觉这次赛制的改变了。。
题目难度是小了。但是时间太短了。。
而且事先准备好一些工具库要占很大便宜。。。