C/C++教程

cf896 B. Ithea Plays With Chtholly

本文主要是介绍cf896 B. Ithea Plays With Chtholly,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题意:

交互题。有n个位置,m次输入,和一个上限c。每次读入一个数x,输出把x放到哪个位置(可以覆盖)。目标是n个位置上都有数且单调不减。

\(1\le x\le c, 1\le c\le 1000,1\le n\cdot \lceil \frac c2 \rceil \le m \le 1000\)

思路:

先考虑一种朴素放法:对于每个x,从左到右找第一个空的或者比x大的位置放上去。那么每个位置最多放c次,n个位置不超过nc次。

考虑另一种放法:若x小于c/2,从左到右找第一个空的或者比x大的位置放上去;否则,从右到左找第一个空的或者比x小的位置放上去。这样任何时候数列都形如 “数数数空空数数数数”,每个位置最多放c/2次,能满足题目的范围。

const signed N = 1003;
int n, m, c, cnt, a[N];

signed main() {
    cin >> n >> m >> c;
    while(cnt < n) {
        int x; cin >> x;
        if(x <= c/2) {
            int p = 1; while(a[p] && a[p] <= x) p++;
            if(!a[p]) cnt++;
            a[p] = x; cout << p << endl;
        }
        else {
            int p = n; while(a[p] && a[p] >= x) p--;
            if(!a[p]) cnt++;
            a[p] = x; cout << p << endl;
        }
    }
}

这篇关于cf896 B. Ithea Plays With Chtholly的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!