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

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;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118389.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 推荐书籍:FFmpeg从入门到精通

    推荐书籍:FFmpeg从入门到精通本书是一本介绍FFmpeg的实战技术指南,全书共10章,分为两个部分。第一部分部分(第1~7章)为FFmpeg的命令行使用篇,介绍了FFmpeg的基础组成部分、FFmpeg工具使用、FFmpeg的封装操作、FFmpeg的转码操作、FFmpeg的流媒体操作、FFmpeg的滤镜操作、FFmpeg的设备操作。第二部分(第8~10章)为FFmpeg的API使用篇,介绍了FFmpeg封装部分的API使用操作、FFmpeg编解码部分的API使用操作,FFmpeg滤镜部分的API使用操作,相关操作均以实例方式进行

  • 中国90后福布斯排行榜前30_2019中国90后十大富豪榜

    中国90后福布斯排行榜前30_2019中国90后十大富豪榜作者|佩奇出品|区块链大本营(blockchain_camp)近日,福布斯发布“Forbes30Under30Asia2019”金融和风险投资类榜单…

  • sql smallint与int_datetime数据类型

    sql smallint与int_datetime数据类型使用整数数据的精确数字数据类型。bigint数值范围从-2^63(-9223372036854775808)到2^63-1(9223372036854775807)的整型数据(所有数字)。存储大小为8个字节。int数值范围从-2^31(-2,147,483,648)到2^31-1(2,147,483,647)的整型数据(所有数字)。存储大小为4个字节。int的SQL-92同义字为integer。smallint数值范围从-2^15(-32,76

  • 【gTest】gtest简介及简单使用

    【gTest】gtest简介及简单使用【gTest】gtest简介及简单使用gtest是一个跨平台(Liunx、MacOSX、Windows、Cygwin、WindowsCEandSymbian)的C++测试框架,有google公司发布。gtest测试框架是在不同平台上为编写C++测试而生成的。从http://code.google.com/p/googletest/downloads/detail?name=gtest-1.7.0.zip&can=2&q=下载最新的gtest-1.7.0版本在Windows下编

  • anconda安装pycharm_在anaconda中安装pycharm

    anconda安装pycharm_在anaconda中安装pycharm在pycharm新建conda环境的前提是安装并配置好anaconda结果建的时候报错:PackagesNotFoundError:Thefollowingpackagesarenotavailablefromcurrentchannels:原因是anaconda的镜像源中没有我们想要的包,所以要把anaconda镜像源换掉。anaconda镜像源的位置在C:\Users\60203_000\.condarc #每个人路径名会有不同打开之后是这样的,换成show_ch

  • 缓存

    缓存

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号