题1  Noip的快乐

(happy.pas/c/cpp)

【问题描述】

    终于到了一年一度的Noip比赛了，多么令人期待和兴奋的一天！其实，人们最高兴的还不是遇见老朋友，而是结交新朋友。可是结交新的朋友就需要很多时间，而除了考试之外时间并不多。例如小L，他在NOIP的入口处等待开门时，决定趁机和其它市县的牛们多套近乎。可是队伍太长，且人们都很自觉的站成仅仅一列，而小L又很想多交不同地方的朋友，因此小L想知道他在哪一个区域内可以结交到最多的不同地方的朋友。当然，这个区域不能太大，否则还没考试他就累死了。

    现在有n个人，题目给出了他们每个人所在市县的编号。他们站在一个从左向右的队伍中。小L不在队列中。他想找到一个长度不超过D的区域，使他能够找到最多的不同地方的朋友。要求输出能找到的朋友所在不同市县的最大数和找到这些朋友的最小区间长度。比如在整个队伍内他按从左向右顺序找到了3个A地朋友，1个B地朋友，1个C地朋友。假设D = 5，那么不同市县的最大数为3（A地、B地、C地），最小区间长度为3（只须结交A地的最右面的一个人即可得到最大市县数3，因此区间长度不是5而是3）。假设在队伍内的人他都还没有结交。

【输入格式】happy.in

    输入文件第一行为两个正整数n，D。分别表示队伍人数和他想找到的最长的区间长度。

    接下来的n行，每行有一个整数，表示每个人所在市县的编号（从左向右）。

【输出格式】happy.out

    输出数据为一行，这行有两个整数，用空格分开，按顺序分别代表能找到的朋友所在不同市县的最大数和找到这些朋友的最小区间长度。

【输入样例】

    5 4

    1

    1

    1

    2

    3

【输出样例】

    3 3

【数据规模】

    对于 100% 的数据，保证5<=n<=1000000, 1<=D<=n, 所有市县编号不超过32767。

   本题出自长乐2012.7.11.1...由于是原创题大概也没有人会来搜题解嗯~~那我就可以尽情的讲废话啦...hahaha~~
   首先先夸一下长乐2012的题质量实在是好到想一口气给他18个赞!!
   就说这一题吧，学到的东西就有很多

   刚开始想到的是用数组模拟队列没想到T掉了...看了题解之后才知道原来用了指针这个神奇的东西！
   虽然原理还是队列，但是确实快了很多！神奇~~

   （ps:表示最近语文有点退化，刚开始有点看不懂题目= =由于考虑到本人常年不听语文课，决定在目前自己还看得懂题目的情况下说一下题目的意思：d:是指最大允许的区间；现在要找在这个区间之内可以找到的最大的城市个数，但是由于最大的城市个数可能<=d,所以还要找到最大的城市个数所在的区间....

    orz...上帝保佑我个语文逗比的孩纸之后还能看得懂我现在在说什么。。好忧伤

大神的题解：

 Noip的快乐

这个题目和某年某省省选题目十分相像，采用队列数据结构，用I,J两个指针过一遍，O(n)算法即可AC.每次都inc(I)(对于PASCAL)（i++，对于C/C++），即可。当发现I,j之间的长度超过了D，或者右面的第i个的省市和左面的第j个的省市相同，j指针++(inc(j)，对于PASCAL)。同时随时刷新一个存储某个市县编号在区间[I,j]中出现的次数，根据I,j的变化而随时变化。如果成了0，将最大市县数减1，如果等于1，最大市县数加一并随时记录最值。

具体实现是这样的：

1.调用两个数组a[1000000],b[32767]

  a[i]就是读入的城市编号，b[i]用来储存在i城市中的人数；

2.k用来储存在区间下不同的城市个数

3.max:在区间下最大的城市个数；min:最大城市个数需要的最短区间（这两个值是不断更新的

附上代码：

#include<cstdio>
#include<cstring>
using namespace std;
int a[3000000],b[32768];
int main()
{
    int i,j=1,max=0,min=1234567890;
    int n,maxd,k=0;
    
    freopen("happy.in","r",stdin);
    freopen("happy.out","w",stdout);
    memset(b,0,sizeof(b));
    scanf("%d%d",&n,&maxd);
    
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    
    i=1;
    while (i<=n)
    {
        b[a[i]]++;
        if (b[a[i]]==1) k++;
        while ((b[a[j]]>1) || ((i-j+1)>maxd))
        {
            b[a[j]]--;
            if (b[a[j]]==0) k--;
            j++;
        }
        if (k>max) 
        {
          max=k;
          min=i-j+1;
        }
        if  ((k==max)&& (min>i-j+1))  min=i-j+1;
        
        i++;
    }
    printf("%d %d",max,min);
    
    return 0;
}

source

之前写p从来没有注意过优先级问题。。
这次被坑了一次。。mark
还好自己在调试的时候发现，
    if  ((k==max)&& (min>i-j+1))  min=i-j+1;
        这个之前没有加括号的语句，在运行之后k神奇的变成了0...orz
下次注意...这种傻逼错误不要犯啦嗯~~

mark

2012.7.11happy,布布扣,bubuko.com

2012.7.11happy