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

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

BusAccepted : 63 Submit : 514Time Limit : 1000 MS Memory Limit : 65536 KB 
题目描述
小强刚来到长沙这个大城市，发现这里有很多他老家没有的东西，其中一个就是公交车了。小强的家到学校有很多个公交站，每个公交站都有一个英文名字。小强很喜欢坐公交车，但是他有个奇怪的要求，就是公交车的上车站和下车站的英文名字必须是首字母相同的，且不在同一个站上下车，不然小强宁愿走过这个站去搭下一趟车，甚至直接走到学校。给出小强从家里到学校的之间每一个公交站的英文名字，问如果不往回走，小强最多能搭几次公交车？
输入
多组样例，每组样例第一行为非负整数n(n<=1000)，表示小强家里到学校之间有n个公交站。接下来n行，每行有一个英文名字，每行不超过100字符。
输出
对于每组样例,输出最多的乘坐次数。
样例输入
4shaoshanerzhongshangxiadongmen5shaoshanshangxiaertianerzhongdongmen
样例输出
12
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);}elseprintf("0\n");}return 0;}