14042: 【原4042】面包要约会

题目描述

author: MW 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4042

Sample Input 1

2
4 7


Sample Output 1

3


Sample Input 2

3
4 3 1


Sample Output 2

9


FineArtz's solution

/* 面包要约会 */
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

constexpr int MAXN = 3e5 + 5, MOD = 1e9 + 7;
int n;
long long x[MAXN];

int main(){
cin >> n;
for (int i = 1; i <= n; ++i) cin >> x[i];
sort(x + 1, x + n + 1);
long long ans = 0, doub = 1, sum = 0;
for (int i = 2; i <= n; ++i){
sum = sum * 2 % MOD;
sum = (sum + x[i - 1]) % MOD;
doub = doub * 2 % MOD;
ans = (ans + (doub - 1) * x[i] - sum) % MOD;
}
cout << ans << endl;
return 0;
}


ligongzzz's solution

#include "iostream"
#include "cstdio"
using namespace std;

constexpr long long mod = (long long)(1e9 + 7);

int pos[300009] = { 0 };

template <class T, class T_val = decltype(*declval<T>()),
class Compare = bool (*)(T_val, T_val)>
void quick_sort(T start, T end,
Compare cmp = [](T_val a, T_val b) {return a < b; }) {
if (start == end)
return;
auto i = start, j = end;
--j;
if (i == j)
return;
//交换
auto key = *start;
for (bool status = true; i != j;) {
if (status) {
if (cmp(*j, key)) {
*i = *j;
++i;
status = false;
}
else
--j;
}
else {
if (cmp(key, *i)) {
*j = *i;
--j;
status = true;
}
else
++i;
}
}
*i = key;
//递归
quick_sort(start, ++i, cmp);
quick_sort(i, end, cmp);
}

int main() {
int n;
cin >> n;

for (int i = 0; i < n; ++i)
scanf("%d", &pos[i]);

quick_sort(pos, pos + n);

long long ans = 0, cur_ans = 0, cnt = 0;

for (int i = 1; i < n; ++i) {
cnt = (cnt * 2 + 1) % mod;
cur_ans = (cur_ans * 2 + (pos[i] - pos[i - 1]) * cnt) % mod;
ans = (ans + cur_ans) % mod;
}

cout << ans;

return 0;
}


skyzh's solution

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const long long M = 1e9 + 7;
inline long long fast_expr(long long a, long long b) {
long long sum = 1;
while (b > 0) {
if (b & 1) sum = (sum * a) % M;
b >>= 1;
a = (a * a) % M;
}
return sum;
}
int main() {
int n;
int pos[300000];
long long sum = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &pos[i]);
sort(pos, pos + n);
for (int i = 0; i < n; i++) {
long long addend = fast_expr(2, i) - fast_expr(2, n - i - 1);
sum = (sum + (addend * pos[i] % M)) % M;
}
sum = (sum + M) % M;
cout << sum << endl;
return 0;
}