codeforces 31 C. Schedule

Posted by 111qqz on Tuesday, December 29, 2015

TOC

http://codeforces.com/problemset/problem/31/C
题意:给出n个借用教室的时间安排,可能会有冲突。要求恰好去掉一个时间安排使得剩下的时间安排不冲突。问多多少种方案。
思路:首先一个直觉是。。除非初始就没有任何冲突。。不然这个答案不会很大。。

如果没有任何冲突,那么答案为n,直接输出一遍就好。

以l为第一关键字,r为第二关键字升序sort下。

如果有一个冲突,那么要看是否有包含关系,如果有,需要去掉大的这个,方案数为1.如果只是相交,那么可以去掉任意一个。方案数为2.

如果有两个冲突,我要看这两个冲突涉及到几个时间安排,如果涉及到4个或者时间安排,那么不可能全部解决,die掉。

如果这两个冲突涉及到三个时间安排,也就是说中间的和两段的相交,那么可以取消中间的这个时间安排来解决冲突。方案数为1.

需要注意的是输出的时候要按照原来的顺序。。所以存的时候记得存一下id.因为排序以后会打乱原有。输出之前还要sort下。 忘了这个。。WA#22/。因为按照id未必是从小到大输出的。

/* ***********************************************
Author :111qqz
Created Time :2015年12月29日 星期二 21时37分11秒
File Name :code/cf/problem/31C.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=5E3+7;
int n ;
int ans[N];

struct node
{
    int fst,sec;
    int id;

    bool operator <(node b)const
    {
    if (fst<b.fst) return true;
    if (fst==b.fst&&sec<b.sec) return true;
    return false;
    }
}a[N];
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif
    cin>>n;
    for ( int i = 1 ; i <= n ; i++) cin>>a[i].fst>>a[i].sec,a[i].id = i ;

    sort(a+1,a+n+1);

//	for ( int i = 1 ; i <= n ; i++) cout<<a[i].fst<<endl;
    a[n+1].fst = inf;
    int num = 0 ;
    bool ill=false,die=false;
    for ( int i = 1 ; i <= n ; i++)
    {
        int j = i+1;
        int cnt =  0;
        while (a[j].fst<a[i].sec&&j<=n)
        {
    //	cout<<"i:"<<i<<" j:"<<j<<endl;
        if (ill)
        {
            die = true;
            break;
        }
        j++;
        cnt++;
        }
        if (die) break;
	    
        if (cnt==0) continue;
        ill = true;
        j--;
	    
        if (cnt>=2)
        {
        num++;
        ans[num] = a[i].id;
        }
        else
        {
        if (a[j+1].fst<a[j].sec&&j+1<=n)
        {
            num++;
            ans[num] =  a[j].id;
            i++;
        }
        else
        {
            num++;
            ans[num] =  a[i].id;
            num++;
            ans[num] =  a[j].id;
        }
        }
    }
    if (die)
    {
      //  cout<<"wwwww"<<endl;
        puts("0");
        return 0;
    }
    if (!ill)
    {
        cout<<n<<endl;
        for ( int i = 1 ; i <= n-1 ; i++) printf("%d ",i);
        printf("%d\n",n);
    }
    else
    {
        cout<<num<<endl;
        sort(ans+1,ans+num+1);  //id的顺序未必是升序。所以需要再次sort下。
        for (  int i =1 ; i <= num-1  ; i++) printf("%d ",ans[i]);
        printf("%d\n",ans[num]);
    }

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付