建设网站需要的开发工具,房产信息查询系统官方网站,asp 茶叶网站模板,巴中免费网站建设正题
题目链接:https://www.luogu.com.cn/problem/P6117 题目大意
平面上有2n2n2n的硬币#xff0c;要给每个硬币匹配一个x∈[1,n],y∈[1,2]x\in[1,n],y\in[1,2]x∈[1,n],y∈[1,2]的位置#xff08;不能重复#xff09;。
使得所有硬币和它们匹配位置的曼哈顿距离之和最小…正题
题目链接:https://www.luogu.com.cn/problem/P6117 题目大意
平面上有2n2n2n的硬币要给每个硬币匹配一个x∈[1,n],y∈[1,2]x\in[1,n],y\in[1,2]x∈[1,n],y∈[1,2]的位置不能重复。
使得所有硬币和它们匹配位置的曼哈顿距离之和最小。
1≤n≤105,−109≤Xi,Yi≤1091\leq n\leq 10^5,-10^9\leq X_i,Y_i\leq 10^91≤n≤105,−109≤Xi,Yi≤109 解题思路
先把每个硬币先移进x∈[1,n],y∈[1,2]x\in[1,n],y\in[1,2]x∈[1,n],y∈[1,2]这个范围内然后考虑贪心去把每个硬币匹配。
我们在同一个xxx的硬币如果上下直接能够补充缺口那么肯定优先上下补充。
不然就从左到右考虑那么最左边的肯定往右移动多余/请求空缺记fi,jf_{i,j}fi,j表示位置(i,j)(i,j)(i,j)现在的需求情况即可。
时间复杂度O(n)O(n)O(n) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e510;
ll n,g[N][2],ans;
signed main()
{scanf(%lld,n);for(ll i1,x,y;i2*n;i){scanf(%lld%lld,x,y);if(y2)ansy-2,y2;else ans1-y,y1;if(xn)ansx-n,xn;else if(x1)ans1-x,x1;g[x][y-1];}for(ll i1;in;i){g[i][0]--;g[i][1]--;if(g[i][0]*g[i][1]0){if(g[i][0]0){ll pmin(-g[i][0],g[i][1]);g[i][0]p;g[i][1]-p;ansp;}else{ll pmin(g[i][0],-g[i][1]);g[i][0]-p;g[i][1]p;ansp;}}ansabs(g[i][0])abs(g[i][1]);g[i1][0]g[i][0];g[i1][1]g[i][1];}printf(%lld\n,ans);return 0;
}
