FZU Problem 1230 区间相交有关问题 &&XTU 1151 bus

FZU Problem 1230 区间相交问题 &&XTU 1151 bus

Problem 1230 区间相交问题

http://acm.fzu.edu.cn/problem.php?pid=1230

Problem Description

Input

Output

Sample Input

Sample Output

Source

思路，贪心，按右端点排序，然后从小到大选，第一个肯定要选，区间相交的情况分两种，一种是一个区间被另一个区间所包含，那么选那个区间比较小的那个，为其他区间腾出区间，另外就是不包含的话就以当前区间右端点为基准，直到有区间的左顶点大于它为止，更新当前区间右端点

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=40002;
struct segment
{
    int begin, end;
    segment(int _b=0, int _e=0):begin(_b),end(_e){};
    inline bool operator<( const segment& ss ) const
    {//按照区间的右端点排序
        return end<ss.end || (end==ss.end)&&(begin<ss.begin);
    }
    inline void input()
    {
        scanf("%d %d",&begin, &end);
        if(begin>end)//保证左端点值不比右端点大
            begin^=end, end^=begin, begin^=end;
    }
}seg[maxn];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int i, res=1, limit;
        for(i=0; i<n; i++)
            seg[i].input();
        sort(seg,seg+n);
        limit=seg[0].end;
        for(i=1; i<n; i++)
        {//seg[i].begin<=limit的所有区间都是相互相交的，因为这些区间必然有公共点limit，即某一个区间的右端点
            if(seg[i].begin>limit)
                res++, limit=seg[i].end;
        }
        printf("%d\n",n-res);
    }
    return 0;
}

Bus
Accepted : 63		Submit : 514
Time Limit : 1000 MS		Memory Limit : 65536 KB

题目描述

小强刚来到长沙这个大城市，发现这里有很多他老家没有的东西，其中一个就是公交车了。小强的家到学校有很多个公交站，每个公交站都有一个英文名字。小强很喜欢坐公交车，但是他有个奇怪的要求，就是公交车的上车站和下车站的英文名字必须是首字母相同的，且不在同一个站上下车，不然小强宁愿走过这个站去搭下一趟车，甚至直接走到学校。给出小强从家里到学校的之间每一个公交站的英文名字，问如果不往回走，小强最多能搭几次公交车？

输入

多组样例，每组样例第一行为非负整数n(n<=1000)，表示小强家里到学校之间有n个公交站。接下来n行，每行有一个英文名字，每行不超过100字符。

输出

对于每组样例,输出最多的乘坐次数。

样例输入

4
shaoshan
erzhong
shangxia
dongmen
5
shaoshan
shangxia
ertian
erzhong
dongmen

样例输出

1
2

http://202.197.224.59/OnlineJudge2/index.php/Contest/read_problem/cid/24/pid/1151

和上面那个题一样

思路：按照题意，可以将首字母相同的站当成一个区间。题目就转换成了，从x个区间中，怎样选择让不想交的区间最多。思路是贪心。

代码：

#include <stdio.h>
#include <algorithm>
using namespace std;
struct st
{
	int s,e;
}a[1000002];
char ch[1002][103];
bool cmp(st a,st b)
{
	if(a.e==b.e)
		return a.s<b.s;
	return a.e<b.e;
}
int main()
{
	int i,j,n;
	int tm;
	int w;
	while(scanf("%d",&n)!=EOF)
	{
		tm=0;
		int s;
		for(i=0;i<n;i++)
		{
			scanf("%s",ch[i]);
			for(j=0;j<i;j++)
			{
				if(ch[i][0]==ch[j][0])
				{
					a[tm].s=j;
					a[tm++].e=i;
				}
			}
		}
		if(tm>0)
		{
			s=1;
			w=a[0].e;
			for(i=1;i<tm;i++)
			{
				if(a[i].s>w)
				{
					s++;
					w=a[i].e;
				}
			}
			printf("%d\n",s);
		}
		else
			printf("0\n");
	}
	return 0;
}