Codeforces231 C. To Add or Not to Add(贪心,双指针)

题意:

Codeforces231 C. To Add or Not to Add(贪心,双指针)

解法:

对数从小到大排序,枚举a[i]作为答案,
那么k次操作就是要将<a[i]的变成a[i],
显然先操作a[i-1],然后操作a[i-2],是向左的一段区间.

可以用双指针维护一个左端点j,满足[j,i]可以全部变成a[i],
用i-j+1更新答案即可.

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxm=2e5+5;
int a[maxm];
int n,k;
void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    int ma=-1,val=-1;
    int j=1;
    int tot=0;
    for(int i=1;i<=n;i++){
        int dif=a[i]-a[i-1];
        tot+=(i-j)*dif;
        while(tot>k){
            tot-=a[i]-a[j];
            j++;
        }
        if(i-j+1>ma){
            ma=i-j+1;
            val=a[i];
        }
    }
    cout<<ma<<' '<<val<<endl;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    solve();
    return 0;
}

上一篇:【计算和控制流】30、上机练习:创建并调用函数


下一篇:深度剖析功率电感和普通电感的区别