[数据结构与算法]Codeforces Round #703 (Div. 2) AB

A

有N个堆栈，每个栈都有非负数。
可以进行操作将正数的第i个堆栈减一，传递给下一个堆栈i+1。
操作可以进行任意次。

判断能否让堆栈严格递增。

题解思路

贪心，
考虑最极端的情况，堆栈的最小的情况数从0开始到n-1。
如果前面有多的话，可以将数字全部转移到最后一个堆栈，也符合严格递增。
如果前面有少的话，那就不行了，因为无法给前面补充元素。

用两个前缀和判断就行了。
添加堆栈的时候，判断有没有少元素。

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>

using namespace std;

int main ()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n ,book = 1 ;
        long long sum1 = 0 ,sum2 = 0 ;
        cin>>n;
        for (int i = 1 ; i <= n ; i++ )
        {
            int k;
            cin>>k;
            sum1 += k;
            sum2 += (i-1);
            if ( sum1 < sum2 )
            {
                book = 0;
                continue;
            }
        }
        if (book)
            cout<<"YES\n";
        else
            cout<<"NO\n";
    }
    return 0;
}

B

在二维坐标中给出任意点，求满足与全部点距离之和最小的点有多少个。

题解思路

这里是绝对值之和，千万不要想错了。

绝对值不等式

分成X Y两部分来处理。

当数轴上奇数个点的时候，满足和最小且相等的只有一个点，而偶数则是区间。 找规律。
直接排序，求出符合的区间相乘即可。

中位数构成的区间，满足和最小且相等。

AC代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>

using namespace std;

long long  a[1010];
long long  b[1010];

int main ()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for (int i = 1 ; i <= n ; i++ )
            cin>>a[i]>>b[i];
        sort(a+1,a+1+n);
        sort(b+1,b+1+n);
        if( n % 2 == 1 )
            cout<<"1\n";
        else
            cout<<(a[n/2+1]-a[n/2] + 1 )*(b[n/2+1]-b[n/2] + 1)<<"\n";
    }
    return 0;
}