• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

DoorsBreakingandRepairingCodeForces-1102C(思维)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

You are policeman and you are playing a game with Slavik. The game is turn-based and each turn consists of two phases. During the first phase you make your move and during the second phase Slavik makes his move.

There are ai.

During your move you can try to break one of the doors. If you choose door x is given).

During Slavik's move he tries to repair one of the doors. If he chooses door 0.

The game lasts 10100 turns. If some player cannot make his move then he has to skip it.

Your goal is to maximize the number of doors with durability equal to wants to minimize the number of such doors. What is the number of such doors in the end if you both play optimally?

Input

The first line of the input contains three integers y, respectively.

The second line of the input contains i-th door.

Output

Print one integer — the number of doors with durability equal to 0 at the end of the game, if you and Slavik both play optimally.

Examples

Input
6 3 2
2 3 1 3 4 2
Output
6
Input
5 3 3
1 2 4 2 3
Output
2
Input
5 5 6
1 2 6 10 3
Output
2

Note

Clarifications about the optimal strategy will be ignored.

 

题目链接:https://vjudge.net/problem/CodeForces-1102C

题意:给你一个含有N个数的数组,每一个元素代表一个门的当前防御值

每一次你可以对门攻击x个点数,而一个神仙可以对门进行y个点数的防御值提升。

当一次你对门的攻击使这个门的防御值小于等于0的时候,这个门就坏掉了,神仙也没法修复了。

问:当你和神仙都采取最优的策略的时候,你最多可以砸坏几个门?

思路:

分2种情况

1: X>Y ,这样的话,每一个门你都可以给砸坏。(不用解释吧)

2:当x<=y,这样你的最优策略就是每一次去砸那些当前防御值比你的攻击力x值小的门,一次就可以给砸坏,

而神仙的最优策略使去提升那些当前防御值比你的攻击力x值小的门,一次来减少你的数量。

通过样例我们可以推出公式,如果初始化的时候有cnt个门当前防御值比你的攻击力x值小,那么答案就是(ans+1)/2

 

我的AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define gg(x) getInt(&x)
using namespace std;
typedef long long ll;
inline void getInt(int* p);
const int maxn=1000010;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int n,x,y;
int a[maxn];
int main()
{
    gbtb;
    cin>>n>>x>>y;
    repd(i,1,n)
    {
        cin>>a[i];
    }
    if(x<=y)
    {
        int ans=0;
        repd(i,1,n)
        {
            if(a[i]<=x)
            {
                ans++;
            }
        }
        ans=(ans+1)/2;
        cout<<ans<<endl;
    }else
    {
        cout<<n<<endl;
    }
    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}

MY BLOG:
https://www.cnblogs.com/qieqiemin/


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
TMS320C6000系列DSP之CCS5.5仿真调试发布时间:2022-07-14
下一篇:
C#调用外部程序发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap