递归 队列 优先队列 题解

题目链接   https://vjudge.net/contest/280315#overview

以及Power  o j1053 

1053: 合并果子

题目链接 https://www.oj.swust.edu.cn/problem/show/1053

优先队列从小到大排好，取出前两个，合并，再插入合并之后的

优先队列版本和set版本

multiset是不去重的set

erase是删除

#include<bits/stdc++.h>
using namespace std;
struct node{
int x;
node(){}
node(int x):x(x){}
friend bool operator <(node a,node b)
{
    return a.x>b.x;
}
};
priority_queue<node>q;
int main()
{
    int n,x;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int x;
        scanf("%d",&x);
        q.push(node(x));
    }
    int ans=0;
    while(q.size()!=1)
    {
        int a=q.top().x;
        q.pop();
        int b=q.top().x;
        q.pop();
        ans+=(a+b);
        q.push(a+b);
    }
    cout<<ans;
}

#include <iostream>
#include <stack>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <string.h>
#include <math.h>
#include<set>
using namespace std;
multiset<int>s;
int main()
{
    int n,x;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&x);
        s.insert(x);
    }
    int ans=0;
    while(s.size()!=1)
    {
        int a=*s.begin();
        s.erase(s.begin());
        int b=*s.begin();
        s.erase(s.begin());
        s.insert(a+b);
        ans+=(a+b);
    }
    printf("%d",ans);
}

D - Train Problem I

HDU - 1022

第一个串依次进栈，如果和第二个串开始的相等 就out   

有点像贪心

比如说   5 12345 14325   

  1和第一个相等先in 再  out   变成 2345  4325  

然后一直in  直到 in 首字母相等  4  开始 out   

out 完后栈顶还是和他相等的  继续  out

#include <iostream>
#include <stack>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <string.h>
#include <math.h>
#include<set>
using namespace std;
int main()
{
    int n;
    char str1[10005];
    char str2[10005];
    stack<char>s;
    queue<int>q;
    while(scanf("%d%s%s",&n,str1,str2)!=EOF)
    {
        while(!q.empty())
            q.pop();
        while(!s.empty())
            s.pop();
        int j=0;
        for(int i=0; i<n; i++)
        {
            s.push(str1[i]);
            q.push(1);//in是1
            while(!s.empty()&&s.top()==str2[j])
            {
                s.pop();
                q.push(-1);//out 是-1
                j++;
            }
        }
        if(!s.empty())
            printf("No.\n");
        else
        {
            printf("Yes.\n");
            while(!q.empty())
            {

                if(q.front()==1)
                    printf("in\n");
                else
                    printf("out\n");
                q.pop();
            }
        }
        printf("FINISH\n");


    }
}

E - 士兵队列训练问题

HDU - 1276

一开始理解错题意了

原来是每报一次数判断一次是否大于3

定义了两个队列

来回跑

#include <iostream>
#include <stack>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <string.h>
#include <math.h>
#include<set>
using namespace std;
queue<int>q;
queue<int>p;
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int cas=1; cas<=n; cas++)
        {
            int num;
            num=cas;
           // printf("%d ",cas);
            scanf("%d",&num);
            if(num<=3)
            {
                if(num==1)
                    printf("1\n");
                else if(num==2)
                    printf("1 2\n");
                else if(num==3)
                    printf("1 2 3\n");
                continue;
            }

            while(!q.empty())
                q.pop();
            while(!p.empty())
                p.pop();
            for(int i=1; i<=num; i++)
                q.push(i);
            int flag=0;
            while(q.size()>3)
            {
                int i=0;
                while(!q.empty())
                {
                    i++;
                    if(i%2!=0)
                        p.push(q.front());
                    q.pop();
                }
                if(p.size()<=3)
                    break;
                i=0;
                while(!p.empty())
                {
                    i++;
                    if(i%3!=0)
                        q.push(p.front());
                    p.pop();

                }

            }
            int i=0;
            int a[3];
            while(!q.empty())
            {
                a[i]=q.front();
                i++;
                q.pop();
            }

            while(!p.empty())
            {
                a[i]=p.front();
                i++;
                p.pop();
            }
            sort(a,a+i);
            for(int j=0;j<i;j++)
            {
                if(j!=0)
                    printf(" ");
                  printf("%d",a[j]);
            }
            printf("\n");

        }
    }
}

F - 看病要排队

HDU - 1873

优先队列

定义结构体

按照优先级排序  优先级相同的按照  先后出现的次序排序

模拟一下就可以了

#include <iostream>
#include <stack>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <string.h>
#include <math.h>
#include<set>
using namespace std;
struct node
{
    int youxianji;
    int id;
    node() {}
    node(int x,int y)
    {
        youxianji=x;
        id=y;
    }
    friend operator < (node a,node b)
    {
        if(a.youxianji<b.youxianji)
            return true;
        else if(a.youxianji==b.youxianji)
        {
            return a.id>b.id;
        }
        return false;
    }
};
priority_queue<node>q[10];
int main()
{
    int n;
    int a,b;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i<10;i++)
            while(!q[i].empty())
               q[i].pop();
        char s[10];
        int cas=1;
        for(int i=1; i<=n; i++)
        {
            scanf("%s",s);
            if(s[0]=='I')
            {
                scanf("%d%d",&a,&b);
                q[a].push(node(b,cas));
                cas++;
            }
            else if(s[0]=='O')
            {
                scanf("%d",&a);
                if(q[a].empty())
                    printf("EMPTY\n");
                else
                {
                    printf("%d\n",q[a].top().id);
                    q[a].pop();
                }
            }
        }

    }
}

G - New Year and the Christmas Ornament

CodeForces - 1091A

#include <bits/stdc++.h>
using namespace std;
int main() {
	int y, b, r;
	cin >> y >> b >> r;
	cout << min(y, min(b - 1, r - 2)) * 3 + 3 << endl;
	return 0;
}

I - Ultra-Fast Mathematician

CodeForces - 61A

不相等就1相等就0

#include <iostream>
#include <stack>
#include <stdio.h>
#include <algorithm>
#include <queue>
#include <string.h>
#include <math.h>
#include<set>
using namespace std;
int main()
{
    char s1[105];
    char s2[105];
    scanf("%s",s1);
    scanf("%s",s2);
    int len=strlen(s1);
    for(int i=0;i<len;i++)
    {
        if(s1[i]!=s2[i])
            printf("1");
        else printf("0");
    }
}