Sage‘s Birthday (hard version) -每天一把CF- 20201003

    科技2022-07-21  114

    每天一把CF:2020-10-03(补发一下昨天的)

    文章目录

    题目思路代码实现

    题目

    原题链接:https://codeforc.es/problemset/problem/1419/D2

    思路

    蛮简单的一道题,题目大意是小红想买冰淇淋(题目中是冰球,这里随意了),店中所有的冰淇淋都摆成了一排,现在我们定义:若某个冰淇淋的价格小于其左边一个和右边一个的价格,则我们称其为棒棒的冰淇淋(所以最两边的永远不会满足这个条件)。小红将会买下所有棒棒哒冰淇淋,现在我们可以将这些冰淇淋重新排序,问小红最多会买多少个冰淇淋。

    d1和d2的区别只是d2中会出现价格相同的情况,而d1不会。

    首先思路是一样的,先将所有价格进行排序,根据中间某个分界点我们将整个数组看出两个数组,一个较大的数的数组,一个较小的数的数组。

    在d1中我们是把所有大数按照顺序依次放在奇数位置的,然后在偶数位依次插入小数,这么做的原因是我们能够确定以后插入的每个较小的数一定小于其周围两个较大的数,因为所有数不同嘛。

    但是在d2中却要发生一些变化,看样例65->1 1 2 4 ,如果我们还按照d1的方法去放置大数的话就可能会浪费最大数->4 1 2 1,因此我们将大数反向插入即可。

    代码实现

    #include <iostream> #include <algorithm> using namespace std; #define _for(i,a,b,c) for(int i=(a);i<=(b);i+=(c)) const int MAX = 1e5 + 5; int a[MAX], b[MAX]; int n; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; _for(i, 1, n, 1) cin >> a[i]; sort(a + 1, a + 1 + n); int p = 1, q = n; if (n % 2) { p = n/2; _for(i, 1, n, 1) if (i & 1) b[i] = a[q--]; else b[i] = a[p--]; } else { p = n / 2 - 1; _for(i, 1, n-1, 1) if (i & 1) b[i] = a[q--]; else b[i] = a[p--]; b[n] = a[q]; } int ans = 0; _for(i, 2, n, 2) if (b[i] < b[i - 1] && b[i] < b[i + 1]) ans++; cout << ans << endl; _for(i, 1, n, 1) cout << b[i] << " "; return 0; }
    Processed: 0.011, SQL: 8