枚举算法练习

48 阅读 0 评论 32 点赞

我是靠谱客的博主飘逸黄蜂，最近开发中收集的这篇文章主要介绍枚举算法练习，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

最长平台（简单）

总时间限制: 1000ms 内存限制: 65536kB
描述
已知一个已经从小到大排序的数组，这个数组的一个平台（Plateau）就是连续的一串值相同的元素，并且这一串元素不能再延伸。例如，在 1，2，2，3，3，3，4，5，5，6中1，2-2，3-3-3，4，5-5，6都是平台。试编写一个程序，接收一个数组，把这个数组最长的平台找出来。在上面的例子中3-3-3就是最长的平台。

输入
第一行有一个整数n(n <= 1000)，为数组元素的个数。第二行有n个整数，整数之间以一个空格分开。
输出
输出最长平台的长度。
样例输入
10
1 2 2 3 3 3 4 5 5 6
样例输出
3
来源
D.Gries. The Science of Programming, Springer-Verlag, 1981

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,a[1002],flag=0,num=1;
    cin>>n;
    a[0]=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]==a[i-1])
        {
            num++;
        }
        else
        {
           // cout<<a[i-1]<<num<<endl;
            if(num>flag)
            {
                flag=num;
                num=1;
            }
            else
            {
                num=1;
            }
        }
    }
    if(num>flag)
        flag=num;
    cout<<flag<<endl;
    return 0;
}

铺地毯

描述
为了准备一个独特的颁奖典礼，组织者在会场的一片矩形区域（可看做是平面直角坐标系的第一象限）铺上一些矩形地毯。一共有n张地毯，编号从1到n。现在将这些地毯按照编号从小到大的顺序平行于坐标轴先后铺设，后铺的地毯覆盖在前面已经铺好的地毯之上。地毯铺设完成后，组织者想知道覆盖地面某个点的最上面的那张地毯的编号。注意：在矩形地毯边界和四个顶点上的点也算被地毯覆盖。

格式
输入格式
输入共n+2行。

第一行，一个整数n(0 <= n <= 10,000)，表示总共有n张地毯。

接下来的n行中，第i+1行表示编号i的地毯的信息，包含四个正整数a，b，g，k(0 <= a, b, g, k <= 100,000)，每两个整数之间用一个空格隔开，分别表示铺设地毯的左下角的坐标（a，b）以及地毯在x轴和y轴方向的长度。

第n+2行包含两个正整数x和y，表示所求的地面的点的坐标（x，y）。

输出格式
输出共1行，一个整数，表示所求的地毯的编号；若此处没有被地毯覆盖则输出-1。

样例1
样例输入1
3
1 0 2 3
0 2 3 3
2 1 3 3
2 2
Copy
样例输出1
3
Copy
样例2
样例输入2
3
1 0 2 3
0 2 3 3
2 1 3 3
4 5
Copy
样例输出2
-1
Copy
限制
1s

来源
NOIp2011提高组Day1第一题

#include<bits/stdc++.h>
using namespace std;
struct dt
{
    int x1,x2,y1,y2;
}a[10001];
int main(){
    int n,x,y,a1,b,c,d,flag=0,i;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a1>>b>>c>>d;
        a[i].x1=a1;
        a[i].y1=b;
        a[i].x2=a1+c;
        a[i].y2=b+d;
    }
    cin>>x>>y;
    for(i=n;i>=1;i--)
    {
        if(x>=a[i].x1 && x<=a[i].x2 && y>=a[i].y1 && y<=a[i].y2)
        {
            flag=1;
            break;
        }


    }
    if(flag==1)
        cout<<i<<endl;
    else
        cout<<"-1"<<endl;
    return 0;
}

描述
在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。

面对海量租借教室的信息，我们自然希望编程解决这个问题。我们需要处理接下来n天的借教室信息，其中第i天学校有ri个教室可供租借。共有m份订单，每份订单用三个正整数描述，分别为dj,sj,tj，表示某租借者需要从第sj天到第tj天租借教室（包括第sj天和第tj天），每天需要租借dj个教室。
我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供dj个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑。

借教室的原则是先到先得，也就是说我们要按照订单的先后顺序依次为每份订单分配教室。如果在分配的过程中遇到一份订单无法完全满足，则需要停止教室的分配，通知当前申请人修改订单。这里的无法满足指从第sj天到第tj天中有至少一天剩余的教室数量不足dj个。

现在我们需要知道，是否会有订单无法完全满足。如果有，需要通知哪一个申请人修改订单。

格式
输入格式
第一行包含两个正整数n,m，表示天数和订单的数量。
第二行包含n个正整数，其中第i个数为ri，表示第i天可用于租借的教室数量。
接下来有m行，每行包含三个正整数dj,sj,tj，表示租借的数量，租借开始、结束分别在第几天。
每行相邻的两个数之间均用一个空格隔开。天数与订单均用从1开始的整数编号。

输出格式
如果所有订单均可满足，则输出只有一行，包含一个整数0。否则（订单无法完全满足）输出两行，第一行输出一个负整数-1，第二行输出需要修改订单的申请人编号。

样例1
样例输入1
4 3
2 5 4 3
2 1 3
3 2 4
4 2 4
Copy
样例输出1
-1
2
Copy
限制
每个测试点1s

提示
对于10%的数据，有1≤ n,m≤ 10；
对于30%的数据，有1≤ n,m≤1000；
对于70%的数据，有1≤ n,m≤ 10^5；
对于100%的数据，有1≤n,m≤10^{6,0≤ri,dj≤10}9,1≤sj≤tj≤n。

来源
Noip2012提高组复赛Day2T2

#include <bits/stdc++.h>
const int I=1000005;
int a[I],c[I],l[I],r[I],n,m,x=-1;
long long cf[I];
long long sum;
bool flag=1;
using namespace std;
int main(){

    ios::sync_with_stdio(false);//输入优化 
    cin.tie(0);cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=m;i++){//差分数组 
        cin>>c[i]>>l[i]>>r[i];
        cf[l[i]]+=c[i];
        cf[r[i]+1]-=c[i];
    }
    int j=m;//PAT：从后往前推，只要发现删除哪个后正好符合要求，则其为ans 
    for(int i=1;i<=n;i++){
        sum+=cf[i];//计算每个教室的使用情况 
        if(sum>a[i]){// 
            while(sum>a[i]){//从后往前撤回消息 
                cf[l[j]]-=c[j];
                cf[r[j]+1]+=c[j];
                if(l[j]<=i&&i<=r[j])//PAT：如果一个请求包含了第i个教室，则删除它会影响sum的值 
                    sum-=c[j];
                j--;
            }
            if(flag)x=j,flag=0;//更新x 
            else
                x=min(x,j);
        }
    }
    if(x==-1)cout<<"0";
    else cout<<"-1"<<endl<<x+1;
    return 0;
}