Day9 Day10

昨天去做了之前补的题，发现当时没做出来的题还是有欠缺，可能要重做一遍加深印象。

昨天找了几个CF的题。

CodeForces - 1140C

贪心+优先队列

先把数组按y降序排序，然后优先队列按x升序排序，每次入队，如果队内个数超过k个，队首元素出队，每次操作都维护ans，这样做的好处是你所要乘的y值是不需要花时间去找的，在y值一定的情况下，找的是当前遍历过的中x最大的一部分。

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

struct node
{
    int x,y;
    bool operator<(const node&k)const
    {
        return y > k.y;
    }
}a[300010];

int n,k;
long long ans,sum;

int main()
{
    scanf("%d%d",&n,&k);
    for(int i = 0;i < n; ++i)
        scanf("%d%d",&a[i].x,&a[i].y);
    sort(a,a + n);
    priority_queue<int,vector<int>,greater<int> >q;
    sum = 0; ans = 0;
    for(int i = 0;i < n; ++i)
    {
        q.push(a[i].x);
        sum += a[i].x;
        if(q.size() > k) sum -= q.top(),q.pop();
        ans = max(ans,sum * a[i].y);
    }
    printf("%lld\n",ans);
    return 0;
}

CodeForces - 1143B

递归

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

int tot,n,a[100];

long long f(int x,int flag)
{
    if(x == 1)
    {
        if(flag) return 9;
        else return a[1];
    }
    if(flag) return 9 * f(x - 1,1);
    else
    {
        if(a[x] > 1)
            return max((a[x] - 1) * f(x - 1,1),a[x] * f(x - 1,0));
        else return f(x - 1,1);
    }
}

int main()
{
    scanf("%d",&n);
    int t = n;
    while(t)
    {
        a[++tot] = t % 10;
        t /= 10;
    }
    printf("%lld\n",f(tot,0));
    return 0;
}