序列(array)
题目描述
给定一个长为 (m) 的序列 (a)。
有一个长为 (m) 的序列 (b)，需满足 (0leq b_i leq n)，(sum_{i=1}^m a_ib_i leq D) 且 (b_i) 为整数。
求 (sum b_i + k min_{i=1}^m{b_i}) 的最大值。
输入格式
第一行一个正整数 (T)，表示数据组数。
对于每组数据，第 (1) 行四个整数 (n, m, k, D)。
第 (2) 行 (m) 个整数 (a_i)。
输出格式
对于每组数据，第一行一个整数 (ans)。
数据范围
对于 (15\%) 的数据，(n, m leq 100)。
对于 (30\%) 的数据，(n leq 10^6)，(m leq 100)。
对于另 (30\%) 的数据，(T = 1) 且数据随机。
对于 (100\%) 的数据，(1 leq n leq 10^9)，(1leq k, m leq 2 imes 10^5)，(1 leq D leq 10^{18})，(1leq a_i leq 5000)。
时空限制
时间限制：2s
空间限制：256MB
题解
首先贪心策略，若(a_i le a_j)，则(b_i ge b_j)。把(a)排序，枚举(b)中有多少个是(n)。若到(n)的有(s)，设(b_{s+1}=x)，则答案为$$s*n+x+lfloordfrac{D-nsums_{i=1}a_i-a_{s+1}*x}{sumn_{i=s+2}a_i}
floor$$
去掉(s*n)，是形如(x+alfloordfrac{bx+c}{d}
floor)的，这个函数形如锯齿
三种情况会达到最大值
-
第一个峰
-
最后一个峰
-
结束点
对应到题目上就是
1.尽可能提高(minb)，剩余去提高(b_s)
2.尽可能提高(b_s)，剩余去提高(minb)
3.(minb+1)，剩下全部提高(b_s)
Code
#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll t,n,m,k,d,ans,x,ans1,ans2,ans3,minb,a[200001],sum[200001];
ll calc(int i,int minb) {return n*(i-1)+min((x-minb*(sum[m]-sum[i]))/a[i],n)+minb*(k+m-i); }
int main()
{
freopen("array.in","r",stdin);
freopen("array.out","w",stdout);
scanf("%lld",&t);
while (t--)
{
scanf("%lld%lld%lld%lld",&n,&m,&k,&d);
ans=0;
for (int i=1;i<=m;++i)
scanf("%lld",&a[i]);
sort(a+1,a+m+1);
for (int i=1;i<=m;++i)
sum[i]=sum[i-1]+a[i];
for (int i=1;i<=m;++i) //a[1]~a[i-1]=n
{
x=d-n*sum[i-1];
if (x<0) break;
minb=(x-a[i]*(n+1))/(sum[m]-sum[i])+1;//a[i]~a[n]>=minb
ans1=x/(sum[m]-sum[i-1]);//方案1,使b[s]和b[s-1]~b[m]一样
if (ans1<0) ans1=0;
if (ans1>n) ans1=n;
ans=max(ans,calc(i,ans1));
ans2=min(ans1,(x-min((x-minb*(sum[m]-sum[i]))/a[i],n))/(sum[m]-sum[i]));//b[s]取最大
if (ans2<0) ans2=0;
if (ans2>n) ans2=n;
ans=max(ans,calc(i,ans2));
ans3=min(ans1,minb);//minb在前面已经先加了1
if (ans3<0) ans3=0;
if (ans3>n) ans3=n;
ans=max(ans,calc(i,ans3));
//ans1,ans2,ans3都代表着b[s-1]~b[m]
}
printf("%lld
",ans);
}
fclose(stdin);
fclose(stdout);
return 0;
}