【SinGuLaRiTy-1017】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved.

对于所有的题目: Time Limit: 1s | Memory: 256 MB

第一题：跳舞

题目描述

奶牛舞会开始了。一共有n（n<=10000）头奶牛，编号为1,2，……，n，它们将要按照顺序登台表演。每头奶牛的跳舞时间是给定的，第i头奶牛的舞蹈需要的时间为dur[i]。舞台可以容纳k头奶牛同时跳舞。开始的时候，编号为1,2，……k的奶牛都上台同时跳。当某头奶牛的舞蹈结束以后，它就立刻下台，下一头奶牛立刻登台开始跳。奶牛上台和下台可以认为是瞬间的，不消耗时间。现在给定奶牛们跳舞的总时间为T，即在T以内，所有奶牛的都必须结束舞蹈。请你确定k的最小值。数据保证当k=n时，一定可以在T以内完成所有舞蹈。

输入

第一行给出两个整数N和T。T不超过1百万。

接下来N行，表示奶牛们的舞蹈所花的时间，dur[i]是一个[1,100000]的整数。

输出

一个整数，表示最小的k。

样例数据

题目分析

第一题......并没有什么好说的，用优先队列+线性扫描做就行了。

STD Code

#include<cstring>#include<cstdio>#include<cstdlib>#include<cmath>#include<queue>#include<iostream>#include<algorithm>#define MAXN 10100using namespace std;priority_queue<int,vector<int>,greater<int> >q;int a[MAXN];int n,t;int main(){    scanf("%d%d",&n,&t);    for(int i=1;i<=n;i++)    {        scanf("%d",&a[i]);    }    for(int i=1;i<=n;i++)    {        int j;        for(j=1;j<=i;j++)            q.push(a[j]);        int bowl=0;        while(j<=n&&bowl<=t)        {            bowl+=(q.top()-bowl);            q.pop();            q.push(a[j++]+bowl);        }        while(!q.empty())        {            bowl+=(q.top()-bowl);            q.pop();        }        if(bowl<=t)        {            cout<<i;            return 0;        }    }    return 0;}

第二题：石头剪刀布

题目描述

小明和小新玩石头剪刀布的游戏。小明在这方面是专家，他可以猜到小新下一次出什么。但是他很懒，他几乎每次都出一样的动作。具体来讲，在整个游戏过程中，他最多只变换一次，即可以从始至终只出一种手势，或是在前几次一种手势，在剩下的次数中出另一种手势。现在他们玩N次游戏，告诉你每次小新出什么。问小明最多能赢几次。

输入

第一行一个整数n，表示游戏进行的次数。（1<=n<=100000）

接下来n行，为H,P,或S中的一个。表示小新出的动作。H表示石头，P表示布，S表示剪刀。

输出

一个整数，表示小明最多能赢几次。

样例数据

题目分析

由于题目所给出的小新出拳的动作是有序的（假设有m个），我们只要分别求出第k个动作（1<=k<=m）之前一直出石头、剪刀、布所能够赢的局数

[SinGuLaRiTy] 高一下半期测试