服务器需求

第一行三个正整数n,m,q，分别表示计划的天数，每台服务器能工作的天数和修改次数。

随后一行n个非负整数，第i个数字 $a_i$ 表示原计划第i天需要多少台服务器工作。

随后q行，每行两个正整数 $p_i,c_i$ ，表示把第 $p_i$ 天需要的服务器数目改成 $c_i$ 。

C++14(g++5.4) 解法, 执行用时: 955ms, 内存消耗: 32468K, 提交时间: 2019-11-01 17:11:01

#include "bits/stdc++.h"
typedef long long ll;
int n,q,p;
ll a[400005],t,m;
ll sum;
std::multiset<ll> S;
int main()
{
	scanf("%d %lld %d",&n,&m,&q);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",a+i);
		sum+=a[i];
		S.insert(a[i]);
	}
	printf("%lld\n",std::max(*S.rbegin(),(sum+m-1)/m));
	while(q--)
	{
		scanf("%d %lld",&p,&t);
		sum+=t-a[p];
		S.erase(S.find(a[p]));
		S.insert(t);
		printf("%lld\n",std::max(*S.rbegin(),(sum+m-1)/m));
		a[p]=t;
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 2493ms, 内存消耗: 32500K, 提交时间: 2019-11-08 22:22:27

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,q,p,a[400005],c,m,s;
multiset<ll> S;
int main(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
        cin>>a[i],s+=a[i],S.insert(a[i]);
    cout<<max(*S.rbegin(),(s+m-1)/m)<<endl;
    while(q--)
        cin>>p>>c,s+=c-a[p],S.erase(S.find(a[p])),S.insert(c),cout<<max(*S.rbegin(),(s+m-1)/m)<<endl,a[p]=c;
}

详情