本文共 838 字,大约阅读时间需要 2 分钟。
标签:思维&逻辑
/* 题意:N个数,定义一个混乱度,sum|Hi+1 - Hi|(1 <= i <= N - 1),Hi可以为0, 可以翻转一个连续的符号相同的字串,来减小这个值,即负数字串->正数字串,反之成立, 求可以达到的最小的混乱度。 分析:选择一个区间只会对两个端点产生影响。模拟程序走一遍样例会很清晰。*/#include#include #include using namespace std;const int maxn = 1000005;int h[maxn];int main(){ int N, i; while(scanf("%d", &N) != EOF){ __int64 ans = 0; priority_queue <__int64> q; for(i = 1; i <= N; i++){ scanf("%d", &h[i]); if(i > 1) ans += fabs(h[i] - h[i - 1]); __int64 d = fabs(h[i] - h[i - 1]) - fabs(h[i] + h[i - 1]); q.push(d); } for(i = 0; i < 2 && !q.empty(); i++){ int u = q.top(); q.pop(); if(u > 0) ans -= u; } printf("%lld\n", ans); } return 0;}
转载地址:http://sskxi.baihongyu.com/