Codeforces Round 52.C+求特殊数组

题目链接：http://codeforces.com/contest/1065/problem/C
题目大意：

5个方柱，高度分别为3，1，2，2，4。要把他们切的一样平，且每次切的方块数量不超过5，如图切2刀y=2, y=1。

思路：只要把方块高度排个序，再求一个数组s[]，s[i]表示y=i到y=i+1这层有多少个方块。
如果对于每个i计算都遍历一遍高度时间复杂度为O（n^2）。
这里用了一种O（n）的方法

数组求法：

int n, k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        s[a[i]-1]++;
    }
    sort(a+1, a+n+1);

    for(int i=a[n]-1;i>=0;i--)
    {
        s[i]+=s[i+1];
    }

这样我们只要再模拟一遍就行了。

AC代码

#include<bits/stdc++.h>
using namespace std;

int a[200005];
int s[200005];

int main()
{
    int n, k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        s[a[i]-1]++;
    }
    sort(a+1, a+n+1);

    for(int i=a[n]-1;i>=0;i--)
    {
        s[i]+=s[i+1];
    }

    int sum=0, now=0;
    for(int i=a[n]; i>=1; i--)
    {
        if(now+s[i]>k)
            sum++, now=s[i];
        else
            now+=s[i];

        if(i==a[1])//最小高度不用再切了
        {
            if(now!=0)//处理剩余方块，加now!=0判断防止全部方块一样高
            sum++;
            break;
        }
    }

    cout<<sum<<endl;

    return 0;
}