首先學習壹個生物學的單詞,exon:外顯子,DNA序列中能夠翻譯表達的片段。給出很多外顯子的起始點和終點,求尋找包含最多外顯子的壹條鏈,並且輸出這些外顯子的編號。
解題思路
先把所有外顯子按照起始點的先後排序,相同起始位置的則看終止位置。然後就是壹個壹個查找,如果當前外顯子的終點在下壹個外顯子之後,就跳過當前的;否則就輸出當前外顯子的編號。這裏使用了vector來存儲外顯子。寫了壹段判斷大小的代碼,作為sort()函數的判斷條件,有必要做個標記。
AC源代碼
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;
struct Exon{
int st,ed,index;
}t;
int lessthan(Exon a,Exon b)
{//this function is necessary. Elements are compared based on this function.
if(a.st<b.st)return 1;//First sort by the start point of each exon.
else if(a.st==b.st&&a.ed<b.ed)return 1;//If start is equal, then sort by the end.
else return 0;
}
int main()
{
int i,n;
vector<Exon> exon;
while(cin>>n&&n)
{
int flag[1000]={0},j=0;
memset(flag,0,sizeof(flag));
while(!exon.empty())
exon.pop_back();//remember to empty the vector!!!
for(i=0;i<n;i++){
cin>>t.st>>t.ed;
t.index=i+1;
exon.push_back(t);
}
sort(exon.begin(),exon.end(),lessthan);
int tail=-1;
for(i=0;i<n-1;i++){
if(exon[i].st>=tail&&exon[i].ed<exon[i+1].ed){
flag[j++]=exon[i].index;
tail=exon[i].ed;
}
else continue;
}
if(exon[n-1].st>=tail)
flag[j]=exon[n-1].index;
cout<<flag[0];
for(i=1;i<=j;i++)
cout<<' '<<flag[i];
cout<<endl;
}
return 0;
}