Codeforces #449 Div2 D

#449 Div2 D

题意

交互式类题目。

起始有 n 张纸，会给出 m 次数字 p ($1 \leq p \leq c$)，每次可选择一张纸，并在纸上写上这个数字，如果纸上已经存在数字，会覆盖掉原来的数字。问不超过 m 次能否使得所有纸上都有数字且不降序排列。

分析

这类想法题挺常见的了，观察数据范围 $ \left \lceil \frac{c}{2} \right \rceil \cdot n \leq m$，我们可以这么理解， $n$ 张纸，每张最多变 $ \left \lceil \frac{c}{2} \right \rceil $ 次。

考虑对于小于 $\left \lceil \frac{c}{2} \right \rceil$ 的数字我们从左往右放，否则从右往左放，且保持数字一直有序。考虑最坏的情况，若依次给出数字 $[\left \lceil \frac{c}{2} \right \rceil, c]$ ，我们都只能填到最右边的纸上，需要改变 $\left \lceil \frac{c}{2} \right \rceil$ 次，其它纸类似。所以对于题目所给出的数据范围我们的贪心策略是有效的。

code

#include<bits/stdc++.h>

using namespace std;

int a[1111];

int main() {

    int n, m, c;

    cin >> n >> m >> c;

    int cnt = 0;

    c = c / 2;

    while(1) {

        int p, pos;

        cin >> p;

        if(p <= c) {

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

                if(!a[i] || a[i] > p) {

                    if(!a[i]) cnt++;

                    a[i] = p;

                    pos = i;

                    break;

                }

            }

        } else {

            for(int i = n; i >= 1; i--) {

                if(!a[i] || a[i] < p) {

                    if(!a[i]) cnt++;

                    a[i] = p;

                    pos = i;

                    break;

                }

            }

        }

        cout << pos << endl;

        fflush(stdout);

        if(cnt == n) break;

    }

    return 0;

}

巴特西

Codeforces #449 Div2 D

#449 Div2 D

题意

分析

code

最新文章

热门文章