想做一个什么样的网站,贵州网络公司网站建设,武进网站建设要多少钱,英文网站建设公司正题
luogu 7405 题目大意
坐标轴上有n个雪球#xff0c;初始重量为0#xff0c;每一条线段上有重量为1的雪#xff0c;当雪球经过时#xff0c;会加上这些雪#xff0c;而地上就没有雪了
共有m个时刻#xff0c;每个时刻会使所有雪球向左/右移动wiw_iwi格#xff…正题
luogu 7405 题目大意
坐标轴上有n个雪球初始重量为0每一条线段上有重量为1的雪当雪球经过时会加上这些雪而地上就没有雪了
共有m个时刻每个时刻会使所有雪球向左/右移动wiw_iwi格问你m个时刻后每个雪球的重量 解题思路
先预处理出前i个时刻最左/最右移动多少
因为雪球之间的距离不会改变所以二分求出相邻两个雪球之间还有雪的最后一个时刻最左最右之间的雪那么就可以知道对于中间这一段左右两个雪球各加了多少重量 代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 200021
using namespace std;
ll n, m, x, l, r, now, a[N], w[N], lm[N], rm[N];
int main()
{scanf(%lld%lld, n, m);for (int i 1; i n; i)scanf(%lld, a[i]);for (int i 1; i m; i){scanf(%lld, x);now x;rm[i] max(rm[i - 1], now);//求最右lm[i] max(lm[i - 1], -now);}for (int i 1; i n; i){l 0;r m;while(l r)//二分{int mid l r 1 1;if (lm[mid] rm[mid] a[i 1] - a[i]) r mid - 1;else l mid;}w[i] rm[l];w[i 1] lm[l];if (l m)//最后一个时刻移动的方向{if (lm[l 1] lm[l]) w[i 1] a[i 1] - a[i] - lm[l] - rm[l];else w[i] a[i 1] - a[i] - lm[l] - rm[l];}}w[1] lm[m];//左边没有雪球w[n] rm[m];for (int i 1; i n; i)printf(%lld\n, w[i]);return 0;
}
