首页 > 其他分享 >NC51101 Lost Cows

NC51101 Lost Cows

时间:2023-05-03 17:45:07浏览次数:56  
标签:cow Lost NC51101 int bound cows brands Cows line

题目链接

题目

题目描述

\(N (2 \leq N \leq 8,000)\) cows have unique brands in the range 1..N. In a spectacular display of poor judgment, they visited the neighborhood 'watering hole' and drank a few too many beers before dinner. When it was time to line up for their evening meal, they did not line up in the required ascending numerical order of their brands.

Regrettably, FJ does not have a way to sort them. Furthermore, he's not very good at observing problems. Instead of writing down each cow's brand, he determined a rather silly statistic: For each cow in line, he knows the number of cows that precede that cow in line that do, in fact, have smaller brands than that cow.

Given this data, tell FJ the exact ordering of the cows.

输入描述

  • Line 1: A single integer, N
  • Lines 2..N: These N-1 lines describe the number of cows that precede a given cow in line and have brands smaller than that cow. Of course, no cows precede the first cow in line, so she is not listed. Line 2 of the input describes the number of preceding cows whose brands are smaller than the cow in slot #2; line 3 describes the number of preceding cows whose brands are smaller than the cow in slot #3; and so on.

输出描述

  • Lines 1..N: Each of the N lines of output tells the brand of a cow in line. Line #1 of the output tells the brand of the first cow in line; line 2 tells the brand of the second cow; and so on.

示例1

输入

5
1
2
1
0

输出

2
4
5
3
1

题解

知识点:树状数组,倍增,枚举。

首先需要一个事实,对于一个排列,要确定其中某个位置的数具体是多少,可以通过整个排列比它小的数字有多少个(或者比它大的数字有多少个)确定。现在这道题确定了各个位置的数的左边比它小的数的个数,我们只需要知道在它右边有多少个数比它小就行,因此我们从右往左枚举,依次确定数字。

首先用树状数组维护右侧出现的数字,随后需要二分一个 \(x\) 通过比较 \(x - cnt_{<x} -1 < a_i\) 得知 \(x\) 是否小了还是大了,从而找到第一个 \(x - cnt_{<x} -1 = a_i\) 的点。注意,条件不能为 \(x - cnt_{<x} -1 \leq a_i\) , 因为可能会出现连续一段刚好等于 \(a_i\) 的点,而我们只需要第一个的下标即可,如果用这个条件,我们得到的是最后一个下标。

当然,这个二分条件其实还可以更简单,我们反过来记录右侧没出现的数字,那么 \(cnt_{<x}\) 直接代表左侧比 \(x\) 小的数字个数,那么条件为 \(cnt_{<x} < a_i\) 即可。

另外,二分套树状数组查询的复杂度是对数平方的,并不是最优的。我们可以直接使用树状数组本身的倍增性质进行二分,是最优的对数复杂度。我封装了两个常用的函数,大于等于 lower_bound 和大于 upper_bound

这道题查询 \(cnt_{<x} = a_i\) 的第一个点,我们 lower_bound 查询即可。

时间复杂度 \(O(n \log n)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template <class T>
class Fenwick {
    int n;
    vector<T> node;

public:
    Fenwick(int _n = 0) { init(_n); }

    void init(int _n) {
        n = _n;
        node.assign(n + 1, T());
    }

    void update(int x, T val) { for (int i = x;i <= n;i += i & -i) node[i] += val; }

    T query(int x) {
        T ans = T();
        for (int i = x;i >= 1;i -= i & -i) ans += node[i];
        return ans;
    }
    T query(int l, int r) { return query(r) - query(l - 1); }

    int lower_bound(T val) {
        int pos = 0;
        for (int i = 1 << __lg(n); i; i >>= 1) {
            if (pos + i <= n && node[pos + i] < val) {
                pos += i;
                val -= node[pos];
            }
        }
        return pos + 1;
    }
    int upper_bound(T val) {
        int pos = 0;
        for (int i = 1 << __lg(n); i; i >>= 1) {
            if (pos + i <= n && node[pos + i] <= val) {
                pos += i;
                val -= node[pos];
            }
        }
        return pos + 1;
    }
};

int a[8007];
int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 2;i <= n;i++) cin >> a[i];
    Fenwick<int> fw(n);
    for (int i = 1;i <= n;i++) fw.update(i, 1);

    vector<int> ans(n + 1);
    for (int i = n;i >= 1;i--) {
        ans[i] = fw.lower_bound(a[i] + 1);
        fw.update(ans[i], -1);
    }
    for (int i = 1;i <= n;i++) cout << ans[i] << '\n';
    return 0;
}

标签:cow,Lost,NC51101,int,bound,cows,brands,Cows,line
From: https://www.cnblogs.com/BlankYang/p/17369445.html

相关文章

  • Codeforces Round #225 (Div. 2) C. Milking cows Greedy
    Iahubhelpshisgrandfatheratthefarm.Todayhemustmilkthecows.Therearencowssittinginarow,numberedfrom1tonfromlefttoright.Eachcowiseitherfacingtotheleftorfacingtotheright.WhenIahubmilksacow,allthecowsthatseet......
  • sqlalchemy 报错 lost connection 解决
    最近在开发过程中遇到一个sqlalchemylostconnection的报错,记录解决方法。报错信息python后端开发,使用的框架是Fastapi+sqlalchemy。在一个接口请求中报错如下:[2023-03-2406:36:35+0000][217][ERROR]ExceptioninASGIapplicationTraceback(mostrecentcalllast)......
  • POJ - 3186 Treats for the Cows(DP)
    题目大意:给你一个数组,每次你可以取两个数中的一个进行操作,要么取数组的第一个,要么数组的最后一个(取完之后,该数删除)假设取出来的数组组成了A现在要求使Sum=A[1]*1+A[2]*2+A[3]*3…+A[n]*n达到最大解题思路:用dp[i][j]表示前面取了i个,后面取了j个最大值则转......
  • Starrocks出现Lost connection to MySQL server during query
    背景:在调度中出现这个报错,但是在后台执行的时候是成功的,每次在调度上执行6分钟即360S的时候出现了这个报错,排查后发现使用的nginx代理中设置的timeout设置的是360s,所以......
  • J - Til the Cows Come Home
    J-TiltheCowsComeHomeBessieisoutinthefieldandwantstogetbacktothebarntogetasmuchsleepaspossiblebeforeFarmerJohnwakesherforthem......
  • Popular Cows
    PopularCowshttp://poj.org/problem?id=2186 思路涉及到有向图的强连通子图检测,参考:https://oi-wiki.org/graph/scc/https://www.cnblogs.com/zwfymqz/p/6693881.h......
  • Til the Cows Come Home ( POJ 2387) (简单最短路 Dijkstra)
    problemBessieisoutinthefieldandwantstogetbacktothebarntogetasmuchsleepaspossiblebeforeFarmerJohnwakesherforthemorningmilking.......
  • POJ--2456 Aggressive cows(二分搜索/最大化最小值)
    记录22:552023-2-9http://poj.org/problem?id=2456reference:《挑战程序设计竞赛(第2版)》3.1.3p142DescriptionFarmerJohnhasbuiltanewlongbarn,withN(2......
  • Troubleshooting gc block lost and Poor Network Performance in a RAC Environment
    Environment:OracleLinuxRedHatLinuxOracle11GOracle12CSymptoms:Highclusterwaitandperformancelossduetoclusterwait.Diagnose:[root@node2......
  • NC25064 [USACO 2007 Mar G]Ranking the Cows
    题目链接题目题目描述EachofFarmerJohn'sNcows(1≤N≤1,000)producesmilkatadifferentpositiverate,andFJwouldliketoorderhiscowsaccording......