Voting Judges(AtCoder agc041_B)

傳送門

題意

現在有$N$個題目,每個題目有一個初始票數,$M$個評委,每個評委可以為$V$個不同的題目投票,投票結束之後選擇分數前$P$個的題目加入到題目集中,詢問某種投票之後使得加入到題目集的題目數最多;

題解

首先將原陣列$(a[i])$進行降序排序,那麼答案一定是從第$P$個位置開始算起。怎麼算呢?記一個字首陣列$b[i]$表示從到達當前位置時,前$i$個位置都投票數變成$a[P]$是花費的總票數。那麼從P位置開始列舉,對於每一個票數可以變為$a[P]$的題目進行判斷,如果不滿足條件就結束。具體判斷看程式碼咯~

AC Code

/*******************************
*   Coder : He Shuo.           *
*   Type : Original Work       *
*******************************/

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;

const int MAXN = 1e5 + 50;

ll N,M,V,P;
ll a[MAXN],b[MAXN],sum;

int main()
{
    scanf("%lld%lld%lld%lld",&N,&M,&V,&P);
    sum = M * V;
    for(int i = 1;i <= N;i ++)scanf("%lld",&a[i]);
	
    ///降序排序
    sort(a + 1,a + 1 + N,greater<ll>());
    ll ans = P;
	///前P-1道題票數拉滿
    sum -= (P - 1) * M;
    
    ///對於每一個可以票數變為a[P]的題目做字首和,表示到當前i位置時前面的票數都變成a[P]花費的總票數;
    for(int i = P;i <= N;i ++)
    {
        if(a[i] + M >= a[P])b[i] = b[i - 1] + a[P] - a[i];
        else break;
    }
    for(ll i = P;i <= N;i ++)
    {
        if(a[i] + M >= a[P])
        {
            ll dis = sum - b[i];///剩下多少票沒投出去;
            ll mx = M - (a[P] - a[i]);///到這裡還可以共同升多少票;
            dis -= mx * (i - P + 1);///共同升票剩下的票數;
            if(dis <= (N - i) * M)ans = i;///若剩下的票數可以盡數投給後面不相干的題目說明可以實現;
            else break;
        }
    }
    printf("%lld",ans);
    return 0;
}