文章标题

╰半夏微凉° 2022-06-09 03:49 257阅读 0赞

售票厅  
【问题描述】  
售票厅出售关于音乐会的票，取代原来的卖一张票的形式，而是一组座号连续的票。售票室已经收到很多预订。每个预订包含指定最小座号的一组连续的票。  
售票厅不能满足所有这样的订票。如果出售所有这样的订票，那么将会有大量数目的座号为空。于是售票室作了如下的安排和价格策略，如果一个订单被接受并且安排了确定的作为，则预定者必须付全部的票的价格(2元)。如果一个订票被接受，但是被安排的位置与申请的位置不一样（最少有一个位置），那么预定者只需付一半的价格（1元）。  
售票室的目标是最大限度增加售票总收入。  
【编程任务】  
你的任务是编写一个程序，计算出售票厅最大能能获得的收入，并输出对应他们选择的预订中座位的安排方案。  
【输入格式】  
　　第一行包含两个整数M 和L。M(1 ≤M≤ 30 000)表示座位的数量，L(1 ≤L≤ 100)表示每组预订中连续座位的数目。座位纺编号从1到M。第二行包含一个整数N，N(1≤N≤100 000)表示预订的数量，第三行包含N个整数，表示预订，其中该行的第i个整数 z(1 ≤z≤ M-L+1)，表示第i个预订要求从座位号Z开始，到座位号z+L-1结束。  
【输出格式】  
输出的第一行包含一个整数S，表示最大的收入，第二行包含一个整数Q，表示被接受的预订数。  
【输出方案说明】  
Q行描述座位的分配，每行包含一对整数x y，表示买者x购买从编号y开始的一组票。输出时座位号必须严格递增，可能有多种输出方案。  
【输入输出样例】  
ticket.in ticket.out 输出方案说明：  
20 3  
7  
4 2 10 9 16 15 17 9  
6 4 1  
1 4  
2 7  
3 10  
6 13  
5 16

以下题解转载自：[AWCXV的博客][AWCXV]

> 设f\[i\]表示前i个座位能获得的最大利润；  
> 设g\[i\]表示前i个座位安排了几个人的预定(有可能是随便找个预定放在前面以赚取1元钱);  
> 设h\[i\]表示前i个座位有多少个预定是随便找一个人预定的(即不是符合它要求的);  
> 再设一个bo\[i\]表示是否有一个人的预定的连续的座位的最后一个座位在i号座位；  
> 我用程序讲

rep1(i,l,m)//枚举座位
        {
            if (g[i-l] <n)//如果i-l的位置安排的预定数小于n
            {
                if (bo[i])//如果有一个预定的连续的座位的最后一个位置在i号
                {
                    f[i] = f[i-l]+2;//则可以安排这个人的需求;
                    g[i] = g[i-l]+1;//安排的预定数递增
                    temp[i] = temp[i-l];//这个过程没有增加不符合要求的人
                }
                else//如果没有人的预定结尾在这里
                {
                    if (f[i]<f[i-l]+1)//就随便找一个人的预定放在这里；
                    {
       //如果更优就更新
                        f[i] = f[i-l]+1;
                        g[i] = g[i-l]+1;
                        temp[i] = temp[i-l]+1;//递增随便预定的人的个数
                    }
                }
            }
            if (bo[i] && g[i-l]==n && temp[i-l]>0)
            {
       //如果有一个人的预定结尾在这里,但是之前的预定已经到达n了,但是前面的座位有一些是随便给的(当前以i结尾的预定肯定也在之前随便给了);
    //那么就把那个之前随便给的预定放在这个地方来,这样总的收益就会增1(之前算作没有按照要求的安排已经增加了1);
                f[i] = f[i-l]+1;
                g[i] = n;//安排的预定数还是不变->这个g数组是用来限制那些随便安排的预定个数的;
                temp[i] = temp[i-l]-1;//随便安排的预定个数递减.
            }
    
            rep1(j,i-l,i-1)//如果不这样循环的话会和程序的预定方案不一样。实际上判断一下f[i-1]是不是大于f[i]就可以了。。看程序吧.
                if (f[j]>f[i])
                {
                    f[i] = f[j];
                    g[i] = g[j];
                    temp[i] = temp[j];
                }

#include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <set>
    #include <map>
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    #include <vector>
    #include <stack>
    #include <string>
    using namespace std;
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define LL long long
    #define rep1(i,a,b) for (int i = a;i <= b;i++)
    #define rep2(i,a,b) for (int i = a;i >= b;i--)
    #define mp make_pair
    #define pb push_back
    #define fi first
    #define se second
    
    typedef pair<int,int> pii;
    typedef pair<LL,LL> pll;
    
    void rel(LL &r)
    {
        r = 0;
        char t = getchar();
        while (!isdigit(t) && t!='-') t = getchar();
        LL sign = 1;
        if (t == '-')sign = -1;
        while (!isdigit(t)) t = getchar();
        while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
        r = r*sign;
    }
    
    void rei(int &r)
    {
        r = 0;
        char t = getchar();
        while (!isdigit(t)&&t!='-') t = getchar();
        int sign = 1;
        if (t == '-')sign = -1;
        while (!isdigit(t)) t = getchar();
        while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
        r = r*sign;
    }
    
    const int MAXN = 3e4+100;
    const int dx[5] = {
       0,1,-1,0,0};
    const int dy[5] = {
       0,0,0,-1,1};
    const double pi = acos(-1.0);
    
    int m,l,f[MAXN],g[MAXN],n,temp[MAXN];
    bool bo[MAXN] = {
       0};
    
    int main()
    {
        //freopen("F:\\rush.txt","r",stdin);
        rei(m);rei(l);
        rei(n);
        rep1(i,1,n)
        {
            int z;
            rei(z);
            bo[z+l-1] = true;
            f[z+l-1] = 2;
            g[z+l-1] = 1;
            temp[z+l-1] = 0;
        }
        rep1(i,l,m)
        {
            if (g[i-l] <n)
            {
                if (bo[i])
                {
                    f[i] = f[i-l]+2;
                    g[i] = g[i-l]+1;
                    temp[i] = temp[i-l];
                }
                else
                {
                    if (f[i]<f[i-l]+1)
                    {
                        f[i] = f[i-l]+1;
                        g[i] = g[i-l]+1;
                        temp[i] = temp[i-l]+1;
                    }
                }
            }
            if (bo[i] && g[i-l]==n && temp[i-l]>0)
            {
                f[i] = f[i-l]+1;
                g[i] = n;
                temp[i] = temp[i-l]-1;
            }
    
            rep1(j,i-l,i-1)
                if (f[j]>f[i])
                {
                    f[i] = f[j];
                    g[i] = g[j];
                    temp[i] = temp[j];
                }
            /*if (f[i-1]>f[i]) 这样写也可以，但是得到的方案会和测试点的方案不一样。认为你错了.. { f[i] = f[i-1]; g[i] = g[i-1]; temp[i] = temp[i-1]; } */
        }
        cout << f[m]<<endl;
        cout << g[m]<<endl;
        return 0;
    }

[AWCXV]: http://blog.csdn.net/harlow_cheng/article/details/53366290