[JZOJ4737] 【NOIP2016提高A组模拟8.25】金色丝线将瞬间一分为二
Description
Input
Output
Sample Input
5 10
1 1
2 2
3 3
4 4
5 5
Sample Output
4
Data Constraint
Hint
开long long 100分,不开10分也是醉了。
long long 卡90分的头一次见。
暴力: 直接O(N^2)不说了。
部分分:x, y坐标递增,设f[i]表示i号点对之前的贡献,那么f[i] = f[i-1] + (abs(x[i] - x[i-1])+ abs(y[i] - y[i-1])) * (i - 1),直接递推就行了。
x坐标相等的不会...
不是正解正确解法。考试的时候不知道怎么yy出来的。
我们把原序列称为p;
我们考虑,一个点i加进来的贡献, 一定是 $ \large \sum_{j=1}^{i-1} |x[i]-x[j]| + |y[i]-y[j]| $.
考虑去掉绝对值,我们先看x轴,y轴和x轴一样。
那么就是如果x[i] > x[j] 贡献 += x[i] - x[j], 否则 贡献 += x[j] - x[i];
受到这个启发(不知脑子里如何蹦出的想法),我们把原数组按照x排序,得到数组p。
然后数组p中的元素的x坐标一定是单调不降的。我们设原来的i在p中的位置为pos[i]。
那么对于j < pos[i] 的元素, 我们可以直接算 $ \large \sum_{ } x[i] - x[j] $。
化简一下得到 $ num * x[i] - \large \sum_{}x[j] $. num表示p数组中1~i中在i前面的数的个数。
所以我们可以用一个树状数组维护数是否出现, 即里面全是01序列。
用另一个树状数组维护$ \large \sum_{ }x[j] $,即扫描到j, 就把x[j]插入树状数组的pos[j]的位置。
对于j > pos[i]的同理。
对于y轴同理。
最后用四个树状数组搞定了这道题。
还有, 这份代码不吸氧气只有80分。
一定记得开long long否则只有10分(论一个人如何让自己的成绩缩小10倍).
复杂度O(NlogN*一个大常数)。
完了我感觉我讲不清了233.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <ctime>
using namespace std;
#define reg register
#define INT long long
#define int long long inline int read() {
int res=;char ch=getchar();bool flag=;
while(!isdigit(ch)){if(ch=='-')flag=;ch=getchar();}
while(isdigit(ch))res=(res<<)+(res<<)+(ch^),ch=getchar();
return flag?-res:res;
}
inline int abss(int x) {return x < ? -x : x;}
int n, D;
struct date {
int x, y, id;
}p[], px[], py[]; struct BIT {
INT tr[];
#define lowbit x & -x
inline void add(int x, int y)
{
while(x <= n) tr[x] += y, x += lowbit;
}
inline INT ask(int x)
{
INT res = ;
while(x) res += tr[x], x -= lowbit;
return res;
}
}x1, x2, y1, y2;//1:是否出现, 2:坐标
INT now; inline bool cmp1(date a, date b)
{
return a.x < b.x;
}
inline bool cmp2(date a, date b)
{
return a.y < b.y;
} int posx[], posy[]; signed main()
{
n = read(), D = read(); for (reg int i = ; i <= n ; i ++) px[i].x = py[i].x = read(), px[i].y = py[i].y = read(), px[i].id = py[i].id = i;
for (reg int i = ; i <= n ; i ++) p[i].x = px[i].x, p[i].y = px[i].y, p[i].id = i;
sort(px + , px + + n, cmp1), sort(py + , py + + n, cmp2);
for (reg int i = ; i <= n ; i ++) posx[px[i].id] = i;
for (reg int i = ; i <= n ; i ++) posy[py[i].id] = i;
for (reg int i = ; i <= n ; i ++)
{
now += x1.ask(posx[i]) * p[i].x - x2.ask(posx[i]);
now += y1.ask(posy[i]) * p[i].y - y2.ask(posy[i]);
now += (x2.ask(n) - x2.ask(posx[i])) - (x1.ask(n) - x1.ask(posx[i])) * p[i].x;
now += (y2.ask(n) - y2.ask(posy[i])) - (y1.ask(n) - y1.ask(posy[i])) * p[i].y;
x1.add(posx[i], ), x2.add(posx[i], p[i].x);
y1.add(posy[i], ), y2.add(posy[i], p[i].y);
if (now >= D) {printf("%d\n", i);return ;}
// printf("%lld\n", now);
}
puts("-1");
return ;
}
最新文章
- 通过Request对象对cookie的设置、获取
- Java集合源码学习(二)ArrayList分析
- markdown 的基本操作
- 上位机控制led
- Table ‘performance_schema.session_variables’ doesn’t exist
- volley(3) 参数{or_barcode:or_barcode,or_remai:or_remain, bar_remain:bar_remain} method:POST
- [转]ASP.NET MVC 入门11、使用AJAX
- reshape2 数据操作 数据融合( cast)
- js之date()对象
- 《java入门第一季》之面向对象(包概述)
- Mybatis之旅第四篇-输入输出映射
- Docker: 快速搭建LNMP网站平台
- HTTPS请求
- C#设计模式之8:外观模式
- Java中 接口是如何实现多态的特性的
- win7系统开机后电脑桌面背景变黑的解决方法
- spring boot(十四)shiro登录认证与权限管理
- HDU1754
- 树莓派编译安装opencv3 (2019.1.6更新)
- 如何将frm格式MYD格式MYI格式文件导入MySQL中