题意:
给你一块正方形的土地,里面有矩形的草地,要求把土地分成两份,满足以下两个条件
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北京)的更多相关文章
-
UVALive7261(2015ACM/ICPC北京赛区现场赛A)
题目链接:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_ ...
-
(HDU 5558) 2015ACM/ICPC亚洲区合肥站---Alice&#39;s Classified Message(后缀数组)
题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=5558 Problem Description Alice wants to send a classi ...
-
2015ACM/ICPC亚洲区长春站 L hdu 5538 House Building
House Building Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) ...
-
2015ACM/ICPC亚洲区长春站 J hdu 5536 Chip Factory
Chip Factory Time Limit: 18000/9000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)T ...
-
2015ACM/ICPC亚洲区长春站 H hdu 5534 Partial Tree
Partial Tree Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)To ...
-
2015ACM/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 ...
-
2015ACM/ICPC亚洲区长春站 F hdu 5533 Almost Sorted Array
Almost Sorted Array Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Ot ...
-
2015ACM/ICPC亚洲区长春站 E hdu 5531 Rebuild
Rebuild Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total S ...
-
2015ACM/ICPC亚洲区长春站 B hdu 5528 Count a * b
Count a * b Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Tot ...
随机推荐
-
OData V4 系列 .net应用
OData 学习目录 添加 OData Client Code Generator 扩展 添加OData T4生成工具 修改 T4 模板的 MetadataDocumentUri 运行Web项目,之后 ...
-
nfs文件系统挂载错误及解决方法
挂载nfs时出现如下错误: 原因: 没有安装nfs客户端相关 解决方法: apt-get install nfs-common 参考资料: http://askubuntu.com/questions ...
-
使用Storm实现实时大数据分析
摘要:随着数据体积的越来越大,实时处理成为了许多机构需要面对的首要挑战.Shruthi Kumar和Siddharth Patankar在Dr.Dobb’s上结合了汽车超速监视,为我们演示了使用Sto ...
-
《more effective C++》条款10 防止构造函数里的资源泄露
构造函数也可能发生内存泄露,考虑如下程序: class A { public: A(int *p) { if(p!=NULL) num=p; ); //do something } private: ...
-
再谈ORACLE CPROCD进程
罗列一下有关oprocd的知识点 oprocd是oracle在rac中引入用来fencing io的 在unix系统下,假设我们没有採用oracle之外的第三方集群软件,才会存在oprocd进程 在l ...
-
使用LINQ TO XML 创建xml文档,以及读取xml文档把内容显示到GridView例子
首先,准备了一个Model类 using System; using System.Collections.Generic; using System.Linq; using System.Text; ...
-
lamp 相关
1.LAMP = linux + apache + mysql(mariadb/mongodb) + php 2.mysql 安装:先下载安装包: wget -c http://mirrors.soh ...
-
Pandas基本功能之选取索引和过滤
索引.选取和过滤 大部分的查询用法 类型 说明 obj[val] 选取DataFrame的单个列或一组列 obj.ix[val] 选取DataFrame的单个行或一组行 obj.ix[:,val] 选 ...
-
黑电-逻辑地址-0X4EB9FDE3- %o %d %x
****************************************************************************** 编程语言通常规定是以0开头的数字是八进制数 ...
-
Java Lock &; Condition
/* jdk1.5以后将同步和锁封装成了对象. 并将操作锁的隐式方式定义到了该对象中, 将隐式动作变成了显示动作. Lock接口: 出现替代了同步代码块或者同步函数.将同步的隐式锁操作变成现实锁操作. ...