订票的贪心算法

djkpengjun

#include
#include
#include
#include
using namespace std;
bool included(int start, int length, int key)
{
    //头交叉
    if(key>=start && key=start && key+length-1>seatnumber>>unitnum;   
    int *start = new int[reqnum];
    for(int i=0;i>start;
    //降序
    sort(start,start+1,greater());
    vector ivec;   //胜者
    vector remain; //败者
    int acceptnumber=0;
    //第一、计算完全可以接受的套票订单的数量,最大全票数
    for(int i=0;i0 && start+reqnum-1 ivec[it1+1] &&            //不会与后面的产生冲突，保证是增益的
                     (remain[it2]-1)%unitnum::iterator it = ivec.begin();
    while(it != ivec.end())     
    {
        int tempval = *it +unitnum;   //注意这里可不是*it+unitnum-1哦
        //如果在两个已接受订单之间
        if(tempval+unitnum <*(it+1)&&tempval<seatnumber)
            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[0])
        {
            ivec.insert(ivec.end(),temp);
            temp+=unitnum;
            sumnumber++;
        }
    }
    ofstream outfile("pj");
    outfile<<(sumnumber-acceptnumber)+acceptnumber*2<<endl<<sumnumber<<endl;
    for(int i=repindex;i<ivec.size();i++)
        outfile<<i+1<<" "<<ivec<<endl;
    for(int i=0;i<repindex;i++)
        outfile<<i+1<<" "<<ivec<<endl;
    infile.close();
    outfile.close();
    return 0;
}
               
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u3/104733/showart_2128887.html