程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> codeforces_420B_Online Meeting

codeforces_420B_Online Meeting

編輯：C++入門知識

題目大意：

公司要開會，有些人會上線，有些人會下線，只有在任何會議都在場的人才能當leader

現在給你一個片段，要你判斷有哪些人是有可能當leader的

解題思路：

當你退出或者上線的時候有人還在線的話是肯定不能當leader的

另外就是當你確定下線了，別人又上線的時候，你也是肯定不能當leader的

因為我們一開始不知道到底有多少人已經在線上了，所以要倒著走一遍，看有多少人已經在線上了

然後在正著走來判斷。

具體的代碼如下：

/*************************************************************************
    > File Name: 420B.cpp
    > Author: BobLee
    > Mail: [email protected] 
    > Created Time: 2014年04月26日 星期六 18時13分17秒
 ************************************************************************/

#include
#include
#include
#include
#include
#include
using namespace std;

const int maxn = 100000+20;

int n,m;

struct node
{
	char o[5];
	int id;
};

node op[maxn];

int a[maxn];
int b[maxn];
int del[maxn];
void read()
{
	for(int i=1;i<=m;i++)
		scanf(%s%d,op[i].o,&op[i].id);
}

void solve()
{
    memset(b,1,sizeof(b)); //b 用來判斷這個人能不能當leader
    memset(a,0,sizeof(a)); //a 用來記錄這個人在最開始的是不是在會議上
    int tot = 0;
    for(int i=m;i>=1;i--)  //從尾巴往前遍歷，看到退出了，那就說明之前在會議上，然後當遇到之前登陸的時候，就說明在之前不在會議上
    {
        if(op[i].o[0]=='-')
        {
            a[op[i].id] = 1;
        }
        else
            a[op[i].id] = 0;
    }
    //也就是說tot就是用來記錄這個片段最開始之前到底有多少人在線上
    for(int i=1;i<=n;i++)
    {
        if(a[i])
            tot++;
    }
    int last = 0;//用來記錄在遍歷過程中最後一個人是誰
    for(int i=1;i<=m;i++)
    {
        /*
         * 這裡用了2個變量來判斷這個人能不能當leader
         * del是用來表示當他退出或者登陸的時候有沒有人，有人就是1，沒有就是0
         * b則是用來表示他是否上線過
         */
        if(op[i].o[0]=='-')
        {
            tot--;
            if(tot>0) del[op[i].id] = 1;
            last = op[i].id;
            /*
             * 下面這句話表示如果當你退出的時候不是最後一個片段，並且目前線上沒有人了
             * 那麼你退出代表你就肯定是下線了，那後面的會議你不能參加，那也就是沒有可能參會了
             */
            if(i!=m && !tot)
                b[op[i].id] = 0;
        }
        else
        {
            /*
             * 這句話的意思是當你登陸的時候有人或者在你登陸之前有別人退出過，那麼你就不能當這個leader
             */
            if(tot>0 ||(op[i].id != last && last))
                del[op[i].id] = 1;
            tot++;
            b[op[i].id] = 1;
        }
    }

    int ans = 0;
    /*
     * 能當leader的要求是你不僅在登陸和登出的時候沒人，而且還要在線上
     */
    for(int i=1;i<=n;i++)
    {
        if(!del[i] && b[i])
            ans++;
    }

    printf(%d
,ans);
    bool f=false;
    for(int i=1;i<=n;i++)
    {
        if(!del[i] && b[i])
        {
            if(!f)
            {
                printf(%d,i);
                f=true;
            }
            else
                printf( %d,i);
        }
    }

    printf(
);

}

int main()
{
	while(~scanf(%d%d,&n,&m))
	{
		read();
		solve();
	}
	return 0;
}