POJ 3179 离散化+二维前缀和+枚举(二分?)

Stella981
• 阅读 853

离散化和前缀和以前做过,但是不熟,所以借鉴的lyd的代码(不过好像他也没用二分查找,虽然书上这么写的)不过代码中有一些剪枝和为下一步预处理的的操作可能优化了时间,反正62ms过了。。。

附上代码:

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<set>
 5 #include<vector>
 6 #define INF 1<<30
 7 using namespace std;
 8 vector<int> X,Y;
 9 const int maxn=510;
10 //typedef point pair<int,int>;
11 int sum[maxn][maxn];
12 vector<pair<int,int> >p; 
13 int main(){
14     int C,n,x,y;
15     int a,b;
16     scanf("%d%d",&C,&n);
17     for(int i=1;i<=n;i++){
18         scanf("%d%d",&a,&b);
19         p.push_back(make_pair(a,b));
20         X.push_back(a);
21         Y.push_back(b); 
22     }
23     //排序 
24     sort(p.begin(),p.end());
25     sort(X.begin(),X.end());
26     X.erase(unique(X.begin(),X.end()),X.end());//去重 
27     sort(Y.begin(),Y.end()); 
28     Y.erase(unique(X.begin(),X.end()),X.end());
29     x=X.size(),y=Y.size();
30     X.push_back(INF),Y.push_back(INF);
31     //求二维前缀和 
32     //sum[i][j]是点X[i-1][j-1]的前缀和 
33     int pos=0;
34     for(int i=1;i<=x;i++){
35         for(int j=1;j<=y;j++){
36             sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
37             while(pos<n&&p[pos].first==X[i-1]&&p[pos].second==Y[j-1]){//判断该点是否有草 
38                 sum[i][j]++; 
39                 pos++;
40             }
41         }
42     }
43     //查找 
44     int ans=INF;
45     for(int i=0;i<x;i++){//枚举起点x坐标 
46         int i1=i+1;//终点x坐标 
47         int s=0;//边长 
48         int j=0;//起点y坐标 
49         int j1=1;//终点y坐标 
50         int val=sum[i1][j1]-sum[i][j1]-sum[i1][j]+sum[i][j];
51         while(1){
52             while(val<C&&(i1<x||j1<y)){
53                 s=min(X[i1]-X[i],Y[j1]-Y[j]);
54                 while(X[i1]-X[i]<=s)i1++;//因为sum[i][j]是坐标(x-1,y-1)的前缀和 
55                 while(Y[j1]-Y[j]<=s)j1++;
56                 val=sum[i1][j1]-sum[i][j1]-sum[i1][j]+sum[i][j];
57             }
58             if(val<C)break;//剪枝 
59             ans=min(ans,s+1); 
60             j++;//y坐标+1 
61             if(j==y)break;//y坐标枚举到头了,退出循环 
62             if(j1<=j){ 
63                 j1=j+1;
64                 s=0;
65             }
66             else{
67                 s-=Y[j]-Y[j-1];//边长也相应的减少 
68             }
69             while(X[i1-1]-X[i]>s) i1--;//为下一轮计算做准备
70             val=sum[i1][j1]-sum[i][j1]-sum[i1][j]+sum[i][j];
71         }
72     }
73     printf("%d\n",ans);
74 }
点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Stella981 Stella981
3年前
KVM调整cpu和内存
一.修改kvm虚拟机的配置1、virsheditcentos7找到“memory”和“vcpu”标签,将<namecentos7</name<uuid2220a6d1a36a4fbb8523e078b3dfe795</uuid
Stella981 Stella981
3年前
Python之time模块的时间戳、时间字符串格式化与转换
Python处理时间和时间戳的内置模块就有time,和datetime两个,本文先说time模块。关于时间戳的几个概念时间戳,根据1970年1月1日00:00:00开始按秒计算的偏移量。时间元组(struct_time),包含9个元素。 time.struct_time(tm_y
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Stella981 Stella981
3年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
3年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
Python进阶者 Python进阶者
10个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这