国际大学生程序设计竞赛例题_5.15构造序列

1,题意:构造长度为N的01序列
输入M个命令(B,E,T)(起点1)
要求位置B到E至少有T个1.
输出:1的个数和位置
2,解决:贪心算法.
按照E从小到大排序,从每个E的最后向前放入点,保证点被最多的命令覆盖.
3.实现代码

#include <iostream>
using namespace std;

const int maxn=5010;
const int maxm=3010;


struct node
{
    int b,e,t;
};
node commands[maxm];

//这里配合qsort的使用
int sort(const void* a,const void* b)
{
    node* m=(node*)a;
    node* n=(node*)b;
    if(m->e!=n->e) return m->e-n->e;
    else return m->b-n->b;
}


int cnt; //测试数目
int n;//字符串长度
int m;//命令的个数

int ans;//记录1的个数
int arr[maxn];//记录1的位置
int sum[maxn];//记录当前位置之后1的总个数

void solve()
{
    for(int i=0;i<m;i++)
    {
        int add=0;
        int x=commands[i].b;
        int y=commands[i].e;
        int subNum=sum[x]-sum[y+1];
        while(subNum<commands[i].t)
        {
            //有可能会跨越1,所以这里需要+add;
            while(arr[y])
            {
                sum[y]+=add;
                y--;
            }
            arr[y]=1;
            subNum++;
            add++;
            ans++;
            sum[y]+=add;
            y--;
        }
        if(add!=0)
            for(int j=1;j<=y;j++)
                sum[j]+=add;
    }

}

int main()
{
    freopen("5.15.in","r",stdin);
    freopen("main.txt","w",stdout);
    while(cin>>n>>m)
    {
        ans=0;
        memset(arr,0,sizeof(arr));
        memset(sum,0,sizeof(sum));
        for(int i=0;i<m;i++)
            cin>>commands[i].b>>commands[i].e>>commands[i].t;
        qsort(commands,m,sizeof(node),sort);
        solve();
        cout<<ans<<endl;
        for(int i=1;i<=n;i++)
            if(arr[i]==1)
                cout<<i<<endl;
    }
    return 0;
}