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)


相关推荐

  • 哈哈,你造原来程序猿这么多长处嘛

    哈哈,你造原来程序猿这么多长处嘛

  • hashmap线程不安全问题_什么是线程安全和线程不安全

    hashmap线程不安全问题_什么是线程安全和线程不安全我们都知道HashMap是线程不安全的,在多线程环境中不建议使用,应该使用ConcurrentHashMap,但是其线程不安全体现在什么地方,可能并没有深入理解,本文将对该问题进行解密。

    2022年10月11日
  • 如何解决高并发,秒杀问题[通俗易懂]

    如何解决高并发,秒杀问题[通俗易懂]相信不少人会被这个问题困扰,分享大家一篇这样的文章,希望能够帮到你!一、秒杀业务为什么难做?1)im系统,例如qq或者微博,每个人都读自己的数据(好友列表、群列表、个人信息);2)微博系统,每个人读你关注的人的数据,一个人读多个人的数据;3)秒杀系统,库存只有一份,所有人会在集中的时间读和写这些数据,多个人读一个数据。例如:小米手机每周二的秒杀,可能手机只有1万部,但瞬时进入的流量可能是几百几千万…

  • Java面向对象三大特性学习总结

    Java面向对象三大特性学习总结面向对象的三大特性:封装、继承、多态将对象的属性和实现细节隐藏起来,不让外部程序直接进行访问,将属性私有化,仅对外公开接口,让外部程序通过类提供的方法来对隐藏信息进行访问和操作。好处是外部程序只能通过类规定的方法对数据进行访问,避免外界程序对类内部属性进行破坏。

  • APP运营:盘点八款主流 APP 消息推送工具[通俗易懂]

    APP运营:盘点八款主流 APP 消息推送工具[通俗易懂]在APP日常运营中,基于营销以及推广的目的,我们需要对APP用户推送一些活动信息或重要资讯。常见的消息推送工具分为两种:1、即技术团队自行开发;2、第三方Push工具对于许多创业型公司而言,相对于自行开发,第三方消息推送工具在推送稳定性、精确覆盖性以及成本方面更具有优势,只需要下载并集成SDK就可以实现功能。本文中我们将盘点八款主流第三方APP消息推送工具,希望对大家在A…

  • 联合国世界卫生组织(WHO)认为健康的包括哪些方面?_联合国世界卫生组织把健康定义为

    联合国世界卫生组织(WHO)认为健康的包括哪些方面?_联合国世界卫生组织把健康定义为联合国世界卫生组织(WHO)对健康的定义是,即“健康不仅是没有疾病,而且包括躯体健康、心理健康、社会适应良好和道德健康”。由此可知,健康不仅仅是指躯体健康,还包括心理、社会适应、道德品质相互依存、相

发表回复

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

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