前言

题目难度比较低。第1题直接二分搜索即可，第2题是一个简单的贪心题。这种难度就要争取全a了。

贩卖机

飞飞在一台自动贩卖机上购物，这台贩卖机一次只能投入一个硬币，飞飞觉得这样太麻烦了就不想买了。在按下退币按钮的时候他发现，退还的钱并不是他投入的那x元硬币，而是退出来了一个f(x)的硬币，经过摸索，飞飞发现f(x)和x的关系是 f(x)=x+(b1-x)(b2-x)..(bm-x)。

飞飞翻了兜兜，发现现在还有n枚面值为a1,a2,...,an的硬币，请问投进去然后退币会赚的硬币有几枚？

输入描述

第一行是两个正整数n，m

第二行是n个正整数a1,a2,...,an

第三行是m个正整数b1,b2,..,bm

1≤n,m≤10^5

-2^30≤a,b≤2^30

输出描述

在一行中输出一个整数，代表投进去会赚的硬币个数。

输入
2 2
2 2
2 2
输出
0
说明：显然投入哪一枚硬币都不会有赚

输入
2 2
2 2
1 1
输出
2
说明：这两枚硬币都可以赚

思路和代码

其实就是看f(x)-x的正负即可。即对于每一个a[i]，看b数组里有多少个元素比他小。二分去做。

#include <algorithm>
#include <iostream>
using namespace std;
int n,m;
long long a[100005], b[100005];
int main() {
    cin>>n>>m;
    for(int i = 1; i<=n; i++) cin>>a[i];
    for(int i = 1; i<=m; i++) cin>>b[i];
    sort(b+1,b+m+1);
    int ans = 0;
    for(int i = 1; i<=n; i++) {
        int pos = lower_bound(b+1, b+m+1, a[i])-b;
        if(b[pos]!=a[i]) {
            if((pos-1)%2==0) ans++;
        }
    }
    cout << ans;
}
// 64 位输出请用 printf("%lld")

勇士打怪

最近小强很喜欢玩一款勇士打怪的游戏，勇者和怪物都有一个属性：能力值。当勇者遭遇一个怪物时，战斗方式如下：

如果勇者的能力值不低于怪物的能力值，勇者胜。

否则勇者败。

勇者可以以任意顺序与怪物战斗，当勇者成功击败一只怪物后他可以获得一枚金币，初始时勇者金币数为0，任意时刻勇者手中的金币数不能为负。

勇者可以在任意时刻花费一枚金币，提升1点能力值。

现在小强想知道，勇者手中最多可以有多少金币，怪物可以不打完。

输入描述

第一行两个空格分隔的正整数a,n，分别代表勇者的初始能力值和怪物的数量。

接下来一行n个空格分隔的正整数A;，用来描述第i只怪物的能力值。

1≤n≤10^5 1≤a,A:≤10^5

输出描述

仅一行一个整数表示答案。

输入
1 3
2 2 1
输出
2
说明；击败能力值最低的怪物获得1金币，然后提高1能力值，然后击败剩下两只怪物，手中有2金币。

思路与代码

贪心可知，肯定先打能力值低的怪物是最佳的。所以对怪物按照能力值从小到大排序后模拟题意即可。

#include <iostream>
#include <algorithm>
using namespace std;
long long A, n, ans, cur;
long long a[100005];
int main() {
    cin>>A>>n;
    for(int i = 1; i<=n; i++) {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int i = 1; i<=n; i++) {
        if(A >= a[i]) cur++;
        else {
            long long t = a[i] - A;
            if(t > cur) break;
            else {
                A += t; cur -= t-1;
            }
        }
        ans = max(ans, cur);
    }
    cout << ans;
    return 0;
}
// 64 位输出请用 printf("%lld")