订票的贪心算法

#include
#include
#include
#include
using namespace std;
bool included(int start, int length, int key)
{
    //头交叉
    if(key>=start && key<=start+length-1)
        return true;
    //尾交叉
    if(key+length-1>=start && key+length-1<= start+length-1)
        return true;
    return false;
}
//O(n)复杂度算法
int main()
{
    string file;
    file = "service.in.txt";
    ifstream infile(file.c_str());
    if(!infile)
    {
        cerr<<"can not open the file:"<    }
    string data;
    int seatnumber,unitnum,reqnum;
    infile>>seatnumber>>unitnum;    
    int *start = new int[reqnum];
    for(int i=0;i        infile>>start[i];
    //降序
    sort(start,start+1,greater());
    vector ivec;   //胜者
    vector remain; //败者
    int acceptnumber=0;
    //第一、计算完全可以接受的套票订单的数量,最大全票数
    for(int i=0;i    {
        //第一个无冲突
        if(ivec.empty())
        {
            if(start[i]>0 && start[i]+reqnum-1 <= seatnumber)
            {
                ivec.push_back(start[i]);
                acceptnumber++;
            }
        }else{
            int count=0;
            //检测是否与已接受的冲突
            for(int index=0;index            {
                if(!included(ivec[index],unitnum,start[i]))
                    count++;
            }
            //不冲突则接受
            if(count == ivec.size())
            {
                ivec.push_back(start[i]);
                acceptnumber++;
            }else{
                remain.push_back(start[i]);
            }
        }    
    }
    //第二步、找增益路径，而不是减少路径,总的来说不能减少全票的数目
    int it1=0,it2=0;
    while(  it1!=ivec.size()  )    
    {
        while(it2!=remain.size())
        {
            if(remain[it2]             if(it1+1 != ivec.size() )
            {
                if( remain[it2]<=ivec[it1+1])  //太超前了,及早退出此层循环
                    break;
                else if( remain[it2]-unitnum>ivec[it1+1] &&            //不会与后面的产生冲突，保证是增益的
                     (remain[it2]-1)%unitnum<(ivec[it1]-1)%unitnum )  //余数较小,方便产生更多合理空隙
                        ivec[it1]=remain[it2];
            }else if( (remain[it2]-1)%unitnum<(ivec[it1]-1)%unitnum )  //余数较小,方便产生更多合理空隙
                    ivec[it1]=remain[it2];
            }
            it2++;
        }
        it1++;
    }
    //第三步、计算勉强可以接受的套票订单的数量
    vector::iterator it = ivec.begin();
    while(it != ivec.end())     
    {
        int tempval = *it +unitnum;   //注意这里可不是*it+unitnum-1哦
        //如果在两个已接受订单之间
        if(tempval+unitnum <*(it+1)&&tempval            it=ivec.insert(it+1,tempval);
        else
            it++;
    }
    int sumnumber=0,repindex;
    for(it = ivec.begin();it!=ivec.end();it++)
        sumnumber++;
    repindex = sumnumber;
    if(sumnumber < seatnumber)
    {
        int temp=1;
        while(temp        {
            ivec.insert(ivec.end(),temp);
            temp+=unitnum;
            sumnumber++;
        }
    }
    ofstream outfile("pj");
    outfile<<(sumnumber-acceptnumber)+acceptnumber*2<    for(int i=repindex;i        outfile<    for(int i=0;i        outfile<    infile.close();
    outfile.close();
    return 0;
}