本文主要是介绍POJ3666 nlogn 做法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
呜呜呜我再也不会放弃一个我能理解的题了！就算花几个小时！就算手里还有很多题！
给你一个序列，每次操作你可以让一个数加一或者让一个数减一，问使这个序列不减的最小操作数（具体是啥我也不想看了，大概就是这样,如果是严格递增a[i] - i就变成了不减）
然后有一个结论是改变之后的序列的每个数，一定是原来序列中的某个数。那么离散化之后的n ^２ DP就很显然了
但是！！有一个极其巧妙的nlogn的解法，不太想写sol了，因为这个博客写的太好了
https://blog.csdn.net/lycheng1215/article/details/80089004
有一个值得修改的地方就是xi 是f(x)第一个取最小值时的x
其实从感性来理解挺好想的，严谨的证明就比较难懂了，不过严格来讲还是得看懂证明。
然后就是POJ3666的代码：
int a[maxn];
priority_queue<int> q;int main()
{int n; scanf("%d", &n);rep(i, 1, n) scanf("%d", a + i);int ans1 = 0;rep(i, 1, n){q.push(a[i]);if(!q.empty() && q.top() > a[i]){ans1 += q.top() - a[i];q.pop();q.push(a[i]);}}reverse(a + 1, a + n + 1);while(!q.empty()) q.pop();int ans2 = 0;rep(i, 1, n){q.push(a[i]);if(!q.empty() && q.top() > a[i]){ans2 += q.top() - a[i];q.pop();q.push(a[i]);}}printf("%d\n", min(ans1, ans2));return 0;
}over
这篇关于POJ3666 nlogn 做法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
