题目

Valera is a little boy. Yesterday he got a huge Math hometask at school, so Valera didn't have enough time to properly learn the English alphabet for his English lesson. Unfortunately, the English teacher decided to have a test on alphabet today. At the test Valera got a square piece of squared paper. The length of the side equals n squares (n is an odd number) and each unit square contains some small letter of the English alphabet.

Valera needs to know if the letters written on the square piece of paper form letter "X". Valera's teacher thinks that the letters on the piece of paper form an "X", if:

on both diagonals of the square paper all letters are the same;
all other squares of the paper (they are not on the diagonals) contain the same letter that is different from the letters on the diagonals.
Help Valera, write the program that completes the described task for him.

题意：

图片说明

题解：

如果我们按照题目要求正序考虑的话，很麻烦，因为我们不知道max(0,i-p)应该给谁才行
所以这里有个很巧妙的方法，逆向思维，题目是每次选一个数，减p，每 轮/(防和谐) 操 /(防和谐)作 k次，然后每个数加ai。我们可以这样先设每个竹子最后高度是H，H每次减ai，最后再加p，如果H能大于hi就说明H合法化，就是将题目要求的过程逆向化
现在的操作为：
1，每一个hi减去ai，且保证大于0（因为最小为0）
2.选择k个点让他们增加p

我们一开始对所有数进行排序，排序按照H/a[i]从大到小，然后依次处理，当u.day < i时，说明第i时刻数已经为负，这说明我们给的高度H不能满足题目要求，直接return 0.如果都能满足return 1

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+9;

int n,m,k,p,h[N],a[N];

struct bb {
    int id,h,a,day;
    bool operator < (const bb &b) const {return day>b.day;}
};
bool check(int H) {
    priority_queue<bb>q;
    for(int i=1;i<=n;i++) if(H-m*a[i]<h[i]) q.push((bb){i,H,a[i],H/a[i]});
    for(int i=1;i<=m&&!q.empty();i++) {
        for(int j=1;j<=k&&!q.empty();j++) {
            bb u=q.top(); q.pop();
            if(u.day<i) return 0;    //在i时刻已经<0了 
            u.h+=p, u.day=u.h/u.a;    //加上p，更新剩余天数 
            if(u.h-u.a*m<h[u.id]) q.push(u);    //如果加上后还是危险的那么就再push回去 
        }
    }
    return q.empty(); 
}

signed main() {
    scanf("%lld%lld%lld%lld",&n,&m,&k,&p);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&h[i],&a[i]);
    int l=1, r=1, ans=0;
    for(int i=1;i<=n;i++) r=max(r,h[i]+a[i]*m);
    while(l<=r) {
        int mid=(l+r)/2;
        if(check(mid)) ans=mid, r=mid-1;
        else l=mid+1;
    }
    printf("%lld",ans);
    return 0;
}