#860 div2

A:

题目：

现在存在两个数组 a 和 b， 现在可以进行任意次的交换 ai 和 bi，问你能不能满足 an 是a数组的最大值

bn 是 b 数组的最大值

思路：

贪心的来说，我们让a[n] b[n] 较大的一个数组，放尽可能大的数字，另一个放尽可能小的数字，这样是最优情况。

代码

bool check(int a[])
{
    int mxx = a[n];
    bool flag = true;
    for(int j = 1; j <= n; j++)
    {
        if(a[j] > mxx)
        {
            return false;
        }
    }
    return true;
}

void solved()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= n; i++) cin >> b[i];

    for(int i = 1; i <= n; i++) if(a[i] < b[i]) swap(a[i], b[i]);

    if(check(a) && check(b))
    {
        cout << "YES" << endl;
        return;
    }
    cout << "NO" <<endl;
}

B：

题目:

现在存在 n 天，每天都有一些人抽奖，假如第 x 个人抽奖在第 i 天中了，那么在 i + 1 ~ m 天中不能再抽奖。

问你可能的每天中奖人选，

思路：

从后向前，每次将当天所有人标记为true，前面的抽奖标记过的不能再当作中奖的，

代码

void solved()
{
    st.clear();

    cin >> n;

    for(int i = 1; i <= n; i++)
    {
        int m;
        cin >> m;
        all[i].clear();
        for(int j = 0; j < m; j++)
        {
            int x;
            cin >> x;
            all[i].push_back(x);
        }
    }

    vector<int> ans;

    for(int i = n; i >= 1; i--)
    {
        bool flag = false;
        for(auto x : all[i])
        {
            if(!st[x] && !flag)
            {
                flag = true;
                ans.push_back(x);
            }
            st[x] = true;

        }
    }

    if(ans.size() != n)
    {
        cout << -1 << endl;
        return;
    }
    reverse(ans.begin(), ans.end());

    for(auto x : ans)
    {
        cout << x << " ";
    }
    cout << endl;
}

C：

题目：

现在存在 n 种糖，每种糖有个数 a[i] 个, 每个糖价值为 b[i]，现在你需要包装他们，每包有 d[i] 个，保证 a[i] % d[i] == 0

c[i] = d[i] * b[i] ，希望每相邻两个的 c[i] 尽可能多，问你有多少个标签。

思路：

假设连续的标签 c[i] = d[i] * b[i] = b[i] * d[i], 所以 Tag = c[i] 至少是 lcm(b[1], b[2]…b[n]]) 或者是其倍数

并且 a[i] * b[i] 都是 c[i] 的倍数, 因为 c[i] = a[i] / x[i] * b[i]。所以 gcd(a[1] * b[1]..... a[n] * b[n]) 是c[i] 的倍数

多以 gcd(~) 至少也是 lcm() 的倍数

代码

void solved()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];

    int gc = a[1] * b[1];
    int lc = b[1];
    int ans = 1;

    for(int i = 2; i <= n; i++)
    {
        gc = gcd(a[i] * b[i], gc);
        lc = lcm(b[i], lc);

        if(gc % lc != 0)
        {
            ans++;
            gc = a[i] * b[i];
            lc = b[i];
        }
    }

    cout << ans << endl;

}

D:

题目：

现在给出一个数组，满足数组内所有数字的和 == 0， 可以重新排列这个数组，问你满足这个数组可能的顺序是什么。

思路：

观察这个条件，条件右边是确定的。因为题目满足所有数字的和 == 0，所以如果有整数那么一定有负数，否则都是 0。

都是 0 的情况，是不合法的。对于条件右边考虑 s 为前缀和数组 s[r] - s[l - 1] < max - min

不难发现，我们尽可能的让前缀和小， s[r] 变小, 维持在 0 左右保证， s[r] 不会超过max, s[l] 尽可能的 0 附近，所以一定满足条件。

所以构造前缀，每次如果前缀 > 0，就后面添加一个正数，否则添加一个负数。

代码

void solved()
{
    cin >> n;
    vector<int> a(n + 1);
    vector<int>z, f;

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

    for(int i = 1; i <= n; i++)
    {
        if(a[i] >= 0) z.push_back(a[i]);
        else if(a[i] < 0) f.push_back(a[i]);
    }


    if(f.empty())
    {
        cout << "NO" << endl;
        return;
    }

    int sum = 0;

    cout << "YES" << endl;

    while(!z.empty() || !f.empty())
    {
        if(sum >= 0 && !f.empty())
        {
            cout << f.back() << " ";
            sum += f.back();
            f.pop_back();
        }else
        {
            cout << z.back() << " ";
            sum += z.back();
            z.pop_back();
        }
    }

    cout << endl;

}