济南网站建设与维护,郑州设计公司有哪些,wordpress获取当前子分类,西安中风险地区有哪些题面 分析 此题真是一言难尽。下面这么大一串#xff0c;真的只是在讲一个小模拟。。。此题也是被几个julao反复讲#xff0c;各种五花八门的奇淫巧技#xff0c;什么数学变形#xff0c;树状数组#xff0c;差分#xff0c;单调……好吧#xff0c;我是那种只会30分暴力…题面 分析 此题真是一言难尽。下面这么大一串真的只是在讲一个小模拟。。。此题也是被几个julao反复讲各种五花八门的奇淫巧技什么数学变形树状数组差分单调……好吧我是那种只会30分暴力的人也没理由嫌弃这些我听不懂的做法。 于是看到了一篇极其妙的题解思路是建坐标系然而这位julao的题解的code跑出来只有30pts。借用大佬的图首先以i为横坐标ai为纵坐标建立平面直角坐标系将点全部描在坐标系里并画出yx的直线可以发现点到直线的竖直距离 之和就是我们要求的答案。 然而怎么求不同顺序的答案呢 只需要左右平移这条直线可以发现向左平移在这条直线上方的点到直线的竖直距离会减小1而在这条直线下方或处于直线上的点到直线的竖直距离会 加1。 如果是向右平移显然是恰好相反所以要枚举所有情况只需要将这条直线向一个方向平移n次每次平移一个单位。然而有一个特殊的点n-1假如选择向左平移1~n-1个点的值的计算方式完全不变。但是第n个点会变所以每次平移特殊处理第n个点。 其实你或许已经发现了图象是答案的几何含义本质上我们的平移操作等效于在序列上移动下标。到这里大体思路就已经出现了但是我觉得细节也是比较难懂的或许是我太菜了所以我再稍微补充一下。 1.怎么维护每次移动后的直线上下方的点呢用up,down记录在直线上方下方的点的个数。先预处理点对于初始直线的上下方个数。再维 护一个d[ ]数组每出现一个处于直线上方的点就将这个 d[s](s为这个点到直线的竖直距离)。这 表示在直线上方的距离处s处有d[s]个 点由初中数学知识易证yx向左平移1单位等价于向上平移1单位。所以当我们一共平移了i个单位后我们就需要利用d[i]来更 新在直线上方的点显然在直线上方的点的数量up-d[i]因为本来离初始直线距离为i的点在直线经过i个单位的平移后已经落在 了直线上而不再在直线上方。相应地downd[i] 2.因为ain的所以第n个点本来一定是属于down集的现在相当于它移到了第一个位置只要比1大的就可从down集出来进入up集。3.计算答案的时候是tmpdown-up根据2中所述最后一个点显然属于down集所以它已经被算成了对答案的贡献加一所以真正的更新方式应是tmpdown-up-1.温馨提示1.longlong 2.数组开四倍。我挂了半天最后瞎搞胡乱改错然后过了。01 dalao给我指点了一下因为按照序列的理论上来说d的偏移量是2n而这又是个环所以是4n空间。 代码 #includeiostream
#includecstdio
#includealgorithm
#includecstring
using namespace std;
#define N 4000100
#define ll long long
ll a[N],d[N];
ll n,ans,tmp,up,down;
int main()
{scanf(%lld,n);for(int i1;in;i){scanf(%lld,a[i]);if(a[i]i)tmpa[i]-i,up,d[a[i]-i];else tmpi-a[i],down;} anstmp;for(int i1;in;i){tmpdown-up-1;tmp-n-a[n-i1],tmpa[n-i1]-1;if(a[n-i1]1)up,down--,d[ia[n-i1]-1];downd[i],up-d[i];ansmin(ans,tmp); }printf(%lld\n,ans);return 0;
} 转载于:https://www.cnblogs.com/NSD-email0820/p/9735072.html
