AtCoder Regular Contest 100

C - Linear Approximation

题意：

求

\[\sum_{i=1}^nabs(A_i-(b+i))
\]

\(A_i,b\)给出。

思路：

将括号拆开，变为\(A_i-i-b\)，所以将所有的\(A_i\)减去\(i\)，然后就是一个经典问题了。

Code

#include <bits/stdc++.h>

#define MP make_pair

#define fi first

#define se second

#define sz(x) (int)(x).size()

//#define Local

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

const int N = 2e5 + 5;

int n;

int a[N];

void run() {

    for(int i = 1; i <= n; i++) cin >> a[i], a[i] -= i;

    sort(a + 1, a + n + 1);

    int p = a[(n + 1) / 2];

    ll ans = 0;

    for(int i = 1; i <= n; i++) {

        ans += abs(p - a[i]);

    }

    cout << ans << '\n';

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    cout << fixed << setprecision(20);

#ifdef Local

    freopen("../input.in", "r", stdin);

    freopen("../output.out", "w", stdout);

#endif

    while(cin >> n) run();

    return 0;

}

D - Equal Cut

题意：

给出一个序列\(a\)，长度为\(n,n\leq 2\cdot 10^5\)。现在要切三刀将这个序列分为四段，问最终每段和的最大值减去最小值最小为多少。

思路：

因为只会切三刀，可以考虑单独枚举一刀，然后考虑其它两刀；
那么就考虑枚举中间的那一刀，然后想怎么处理两边的划分。
设左边的两段和为\(L_1,L_2\)，右边的两段和为\(R_1,R_2\)，那么当\(L_1,L_2\)以及\(R_1,R_2\)的差都最小时，答案最优。
简略证明如下：
左端和为\(L\)，右端和为\(R\)，那么不妨\(L_1=\frac{L}{2}+t,L2=\frac{L}{2}-t,R_1=\frac{R}{2}+k,R_2=\frac{R}{2}-k\)，显然\(MAX=max(L_1,R_1),MIN=min(L_2,R_2)\)，那么让\(t,k\)尽量小肯定最优。

其实证明也可以分情况讨论，也就只有两种情况，只是在直觉方面不好感受。。。但这样来想更为自然= =所以矛盾啊QAQ

Code

#include <bits/stdc++.h>

#define MP make_pair

#define fi first

#define se second

#define sz(x) (int)(x).size()

//#define Local

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

const int N = 2e5 + 5;

int n;

int a[N];

ll sum[N];

ll Get(int l, int r, int m) {

    return abs(sum[r] - sum[m] - sum[m] + sum[l - 1]);

}

void run() {

    for(int i = 1; i <= n; i++) {

        cin >> a[i];

        sum[i] = sum[i - 1] + a[i];

    }

    int j = 1, k = 3;

    ll ans = 1e18;

    for(int i = 2; i <= n - 1; i++) {

        while(j < i - 1 && Get(1, i, j) > Get(1, i, j + 1)) ++j;

        while(k < n - 1 && Get(i + 1, n, k) > Get(i + 1, n, k + 1)) ++k;

        ll mx = max(sum[i] - sum[j], max(sum[j], max(sum[n] - sum[k], sum[k] - sum[i])));

        ll mn = min(sum[i] - sum[j], min(sum[j], min(sum[n] - sum[k], sum[k] - sum[i])));

//        cout << j << ' ' << i << ' ' << k << '\n';

        ans = min(ans, mx - mn);

    }

    cout << ans << '\n';

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie(0); cout.tie(0);

    cout << fixed << setprecision(20);

#ifdef Local

    freopen("../input.in", "r", stdin);

    freopen("../output.out", "w", stdout);

#endif

    while(cin >> n) run();

    return 0;

}

E - Or Plus Max

可以参见：传送门

转换的思路还是挺巧妙的。

F - Colorful Sequences

太菜了不会啊。。。

巴特西

AtCoder Regular Contest 100

C - Linear Approximation

D - Equal Cut

E - Or Plus Max

F - Colorful Sequences

最新文章

热门文章