Codeforces Beta Round #10 B. Cinema Cashier (树状数组)

题目大意：

n波人去k*k的电影院看电影。

要尽量往中间坐，往前坐。

直接枚举，贪心，能坐就坐，坐在离中心最近的地方。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define maxn 1000005
#define lowbit(x) (x&(-x))

using namespace std;

struct BIT
{
    int sum;
    void init(){sum=0;}
}bit[105][105];
int q,n;
int Sum(int row,int x)
{
    int ret=0;
    for(int i=x;i>=1;i-=lowbit(i))
        ret+=bit[row][i].sum;
    return ret;
}
int query(int row,int l,int r)
{
    return Sum(row,r)-Sum(row,l-1);
}
void update(int row,int x)
{
    for(int i=x;i<=n;i+=lowbit(i))
        bit[row][i].sum++;
}
int cal(int s,int e)
{
    return (s+e)*(e-s+1)/2;
}
int main()
{
    scanf("%d%d",&q,&n);
    int cen=n/2+1;

    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
        {
            bit[i][j].init();
        }
    for(int i=1;i<=q;i++)
    {
        int num;
        scanf("%d",&num);
        int ansr=-1,ansc=-1;
        int min_val=0x3f3f3f3f;

        for(int r=1;r<=n;r++)
        {
            for(int c=1;c+num-1<=n;c++)
            {
                if(query(r,c,c+num-1)==0)
                {
                    int tmp;
                    if(c>=cen)
                    {
                        tmp=cal(c,c+num-1)-cen*num+abs(r-cen)*num;
                    }
                    else if(c+num-1<=cen)
                    {
                        tmp=cen*num-cal(c,c+num-1)+abs(r-cen)*num;
                    }
                    else
                    {
                        tmp=abs(r-cen)*num+cal(cen,c+num-1)-(c+num-cen)*cen+cen*(cen-c)-cal(c,cen-1);
                    }
                    if(tmp<min_val)
                    {
                        min_val=tmp;
                        ansr=r;
                        ansc=c;
                    }
                }
            }
        }
        if(min_val!=0x3f3f3f3f)
        {
            printf("%d %d %d\n",ansr,ansc,ansc+num-1);
                for(int j=ansc;j<=ansc+num-1;j++)
                    update(ansr,j);
        }
        else puts("-1");
    }
    return 0;
}

Codeforces Beta Round #10 B. Cinema Cashier (树状数组),布布扣,bubuko.com

Codeforces Beta Round #10 B. Cinema Cashier (树状数组)

原文：http://blog.csdn.net/u010709592/article/details/37612775