hihocoder 1249(2015ACM/ICPC北京)

时间:2022-09-08 15:20:05

题意:

给你一块正方形的土地,里面有矩形的草地,要求把土地分成两份,满足以下两个条件

1.两边的绿洲,左边>=右边,差值尽可能的小

2.在满足1的情况下分给左边的土地尽快能的多

而且绿洲不会出现覆盖

思路:

将绿洲压到你给一维矩阵中,然后从左往右加,当ls*2 >= sum,往后面寻找最近的一个p[i] != 0(即存在绿洲的地方)

Orz:

第一次没对,就YY绿洲可能超出了土地范围,然后哦一直WA

现在才发现,当时只是没把有的数定义成long long超了,QAQ心好痛

#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef long long ll;
const int maxn = 10001000;
const int INF = 0x3f3f3f3f;
ll p[maxn]; int main()
{
int n,T,len;
ll sum,lef,top,w,h;
scanf("%d",&T);
while(T--)
{
memset(p,0,sizeof(p));
scanf("%d%d",&len,&n);
sum = 0;
for(int i = 0;i < n;i++)
{
scanf("%lld%lld%lld%lld",&lef,&top,&w,&h);
p[lef] += h;
p[lef+w] -= h;
sum += w*h;
}
ll ls = 0;
for(int i = 1;i <= len;i++)
{
p[i] += p[i-1];
} for(int i = 0;i <= len;i++)
{
ls += p[i];
if(ls * 2 >= sum)
{
int j;
for(j = i+1;p[j]==0 && j < len;j++);
printf("%d\n",j);
break;
}
}
}
return 0;
}

  

hihocoder 1249(2015ACM/ICPC北京)的更多相关文章

  1. UVALive7261&lpar;2015ACM&sol;ICPC北京赛区现场赛A&rpar;

    题目链接:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_ ...

  2. &lpar;HDU 5558&rpar; 2015ACM&sol;ICPC亚洲区合肥站---Alice&&num;39&semi;s Classified Message&lpar;后缀数组&rpar;

    题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=5558 Problem Description Alice wants to send a classi ...

  3. 2015ACM&sol;ICPC亚洲区长春站 L hdu 5538 House Building

    House Building Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others) ...

  4. 2015ACM&sol;ICPC亚洲区长春站 J hdu 5536 Chip Factory

    Chip Factory Time Limit: 18000/9000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)T ...

  5. 2015ACM&sol;ICPC亚洲区长春站 H hdu 5534 Partial Tree

    Partial Tree Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)To ...

  6. 2015ACM&sol;ICPC亚洲区长春站 G hdu 5533 Dancing Stars on Me

    Dancing Stars on Me Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Ot ...

  7. 2015ACM&sol;ICPC亚洲区长春站 F hdu 5533 Almost Sorted Array

    Almost Sorted Array Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Ot ...

  8. 2015ACM&sol;ICPC亚洲区长春站 E hdu 5531 Rebuild

    Rebuild Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)Total S ...

  9. 2015ACM&sol;ICPC亚洲区长春站 B hdu 5528 Count a &ast; b

    Count a * b Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)Tot ...

随机推荐

  1. OData V4 系列 &period;net应用

    OData 学习目录 添加 OData Client Code Generator 扩展 添加OData T4生成工具 修改 T4 模板的 MetadataDocumentUri 运行Web项目,之后 ...

  2. nfs文件系统挂载错误及解决方法

    挂载nfs时出现如下错误: 原因: 没有安装nfs客户端相关 解决方法: apt-get install nfs-common 参考资料: http://askubuntu.com/questions ...

  3. 使用Storm实现实时大数据分析

    摘要:随着数据体积的越来越大,实时处理成为了许多机构需要面对的首要挑战.Shruthi Kumar和Siddharth Patankar在Dr.Dobb’s上结合了汽车超速监视,为我们演示了使用Sto ...

  4. 《more effective C&plus;&plus;》条款10 防止构造函数里的资源泄露

    构造函数也可能发生内存泄露,考虑如下程序: class A { public: A(int *p) { if(p!=NULL) num=p; ); //do something } private: ...

  5. 再谈ORACLE CPROCD进程

    罗列一下有关oprocd的知识点 oprocd是oracle在rac中引入用来fencing io的 在unix系统下,假设我们没有採用oracle之外的第三方集群软件,才会存在oprocd进程 在l ...

  6. 使用LINQ TO XML 创建xml文档,以及读取xml文档把内容显示到GridView例子

    首先,准备了一个Model类 using System; using System.Collections.Generic; using System.Linq; using System.Text; ...

  7. lamp 相关

    1.LAMP = linux + apache + mysql(mariadb/mongodb) + php 2.mysql 安装:先下载安装包: wget -c http://mirrors.soh ...

  8. Pandas基本功能之选取索引和过滤

    索引.选取和过滤 大部分的查询用法 类型 说明 obj[val] 选取DataFrame的单个列或一组列 obj.ix[val] 选取DataFrame的单个行或一组行 obj.ix[:,val] 选 ...

  9. 黑电-逻辑地址-0X4EB9FDE3- &percnt;o &percnt;d &percnt;x

    ****************************************************************************** 编程语言通常规定是以0开头的数字是八进制数 ...

  10. Java Lock &amp&semi; Condition

    /* jdk1.5以后将同步和锁封装成了对象. 并将操作锁的隐式方式定义到了该对象中, 将隐式动作变成了显示动作. Lock接口: 出现替代了同步代码块或者同步函数.将同步的隐式锁操作变成现实锁操作. ...