首页 > 代码库 > SWUN 1763
SWUN 1763
SWUN 1763
题目链接
思路:先把序列排序,然后对于某个最佳答案,肯定有一个位置值是不用变的,那么只要能高效维护每个位置的答案即可,这个只需要从左往右和从右往左各扫一遍,记录下左边和右边答案即可,第二遍扫的时候更新一下最大值即可
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int N = 100005; int n; ll a[N], l[N], r[N]; int main() { while (~scanf("%d", &n)) { ll ans = 1000000000000000LL; for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); sort(a + 1, a + n + 1); a[n + 1] = a[n] + 1; for (int i = 1; i <= n; i++) { l[i] = l[i - 1] + (a[i] - a[i - 1] - 1) * (i - 1); } for (int i = n; i >= 1; i--) { r[i] = r[i + 1] + (a[i + 1] - a[i] - 1) * (n - i); ans = min(l[i] + r[i], ans); } printf("%lld\n", ans); } return 0; }
SWUN 1763
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。