Codeforces Round #437 (Div. 2, based on MemSQL Start[c]UP 3.0

Problem A

水题，水一水。

 #include<bits/stdc++.h>

 using namespace std;

 int n;

 char s[];

 int main()

 {

     cin>>n;

     int cnt1=,cnt2=;

     scanf("%s",s);

     for(int i=;i<n-;i++)

     {

         if(s[i]=='S' && s[i+]=='F') cnt1++;

         else if(s[i]=='F' && s[i+]=='S') cnt2++;

     }

     if(cnt1>cnt2) puts("YES");

     else puts("NO");

     return ;

 }

Problem B

Save the problem!

题目大意：给你数字n，让你给出一个钱的总数m，和钱的种类n个，要求用这些种类的钱

构成m的种数为n。

思路：我是用5和2两种钱构造的，我们考虑构成10 的种数一共只有两种，一种是2 2 2 2 2,另一种是

5 5,那么20 就是三种，30就是四种，40就是五种，一直这样构造下去，忘了考虑一种情况WA了一次。。。

 #include<bits/stdc++.h>

 using namespace std;

 int n;

 int main()

 {

     scanf("%d",&n);

     if(n==)

     {

         puts("1 1");

         puts("");

         return ;

     }

     printf("%d 2\n",(n-)*);

     puts("5 2");

     return ;

 }

Promblem C

Ordering Pizza

题目大意：现在有n个人需要吃si 片披萨，一共有两种披萨A,B，第i个人吃一片A披萨获得的

愉悦值为ai，B为bi，一块披萨能分成S片，我们要买最少的披萨，问你最大愉悦值是多少。

思路：我们先让每个人吃获得愉悦值大的披萨，然后统计A披萨的片数和B披萨的片数，

A和B对S 取膜，剩下的就是不确定的，如果A+B>S则买两种披萨各一个，如果A+B<=S

则买一个披萨，两种披萨都模拟一遍取愉悦值大的。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=1e5+;

ll _abs(ll x)

{

    if(x>=) return x;

    else return -x;

}

struct node

{

    ll s,a,b;

    bool operator < (const node &rhy)const

    {

        return _abs(a-b)<_abs(rhy.a-rhy.b);

    }

}p[N];

ll n,S;

ll work(ll c1,ll c2)

{

    ll ans=;

    if(c1)

    {

        for(int i=;i<n;i++)

        {

            if(p[i].a<p[i].b) continue;

            if(p[i].s>=c1) ans+=c1*(p[i].a-p[i].b);

            else ans+=p[i].s*(p[i].a-p[i].b);

            c1-=p[i].s;

            if(c1<=) break;

        }

    }

    else

    {

        for(int i=;i<n;i++)

        {

            if(p[i].a>=p[i].b) continue;

            if(p[i].s>=c2) ans+=c2*(p[i].b-p[i].a);

            else ans+=p[i].s*(p[i].b-p[i].a);

            c2-=p[i].s;

            if(c2<=) break;

        }

    }

    return ans;

}

int main()

{

    cin>>n>>S;

    ll sum=,ans=;

    ll res1=,res2=;

    for(int i=;i<n;i++)

    {

        scanf("%I64d%I64d%I64d",&p[i].s,&p[i].a,&p[i].b);

        ans+=p[i].s*max(p[i].a,p[i].b);

        if(p[i].a>=p[i].b) res1+=p[i].s;

        else res2+=p[i].s;

    }

    res1=res1%S; res2=res2%S;

    if(res1+res2>S)

    {

        printf("%I64d\n",ans);

        return ;

    }

    ll res=1e18;

    sort(p,p+n);

    res=min(res,work(,res2));

    res=min(res,work(res1,));

    printf("%I64d\n",ans-res);

    return ;

}

Problem E

Buy Low Sell High

题目大意：给你一些股票每天的价格，每一天你可以选择买，卖，或者啥都不干，问你

利润最大多少。

思路：智力题，我不会！用优先队列维护最小值，我们取一个数b，如果这个数比堆顶的

元素a小，则将b加入优先队列，如果b比a大，删除a，加入两个b，(b-a)加入ans，

第一个b相当于把a变成了b，第二个b是自身。

 #include<bits/stdc++.h>

 using namespace std;

 const int N=*1e5+;

 int n,a[N];

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<=n;i++) scanf("%d",&a[i]);

     priority_queue<int,vector<int>,greater<int> > Q;

     long long ans=;

     for(int i=;i<=n;i++)

     {

         if(Q.empty())

         {

             Q.push(a[i]);

             continue;

         }

         int t=Q.top();

         if(t>=a[i]) Q.push(a[i]);

         else

         {

             ans+=a[i]-t;

             Q.pop();

             Q.push(a[i]); Q.push(a[i]);

         }

     }

     printf("%I64d\n",ans);

     return ;

 }

巴特西

Codeforces Round #437 (Div. 2, based on MemSQL Start[c]UP 3.0 - Round 2)

最新文章

热门文章