列表

详情


NC205055. 牛牛爱学习

描述

疫情期间,牛牛宅在家里无事可做,于是就在网上买了n本书,每本书都有一个知识值为ai。每读一本书,牛牛的知识力就会上升ai点。当然了,因为牛牛的精力也是有限的,如果同一天连续读k本书,获得的知识力只能增加ai-k+1点。比如第一天看了知识值为5的书,那么牛牛会获得5点知识力,如果这一天在继续看另一本知识值为5的书,只能获得4点知识力,如果看了前面两本书后在继续看一本知识值为2的书,就只能获得0点知识力。牛牛想知道如果他要获得m点知识力,最少需要看几天。

注意:看书不需要按顺序,一本书只能看一次,书可以不看完,只要看就会增加知识力,当书增加的知识力为负时候可以选择不看,可以认为看完一本书是一瞬间的事情,看完后书就会消失。

输入描述

第一行输入一个n(1≤n≤106)和m(1≤m≤109),第二行输入每本书的知识值ai(0≤ai≤109)。

输出描述

输出最少要多少天才能获得大于等于m点的知识力,如果无法获得,请输出-1。

示例1

输入:

4 10
4 4 4 4

输出:

1

说明:

第一天看完四本书知识力增加 4+3+2+1=10

示例2

输入:

3 20
8 6 6

输出:

3

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 58ms, 内存消耗: 3076K, 提交时间: 2020-09-10 22:16:11

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[1000005],n,m;
ll tot;
bool ck(int x){
	ll s=0;
	for(int i=0;i<n;++i)
		if((s+=a[i]-i/x)>=m)return 1;
	return 0;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;++i)
		scanf("%d",a+i),tot+=a[i];
	if(tot<m)puts("-1");
	else{
		sort(a,a+n,greater<int>());
		int l=0,r=n+1,mid;
		while(l+1<r){
			mid=l+r>>1;
			if(ck(mid))r=mid;
			else l=mid;
		}
		printf("%d",r);
	}
}

C++(clang++11) 解法, 执行用时: 90ms, 内存消耗: 3088K, 提交时间: 2021-03-23 16:09:03

#include <iostream>
#include <algorithm>
using namespace std;
int a[1000005],n,m;
inline bool pd(int x)
{
	long long s=0;
	for(int i=1;i<=n;i++)
		s+=max(0,a[i]-(i-1)/x);
	return s>=m;
}
signed main() {
	cin >> n >> m;
	for(int i=1;i<=n;i++)
		cin >> a[i];
	sort(a+1,a+n+1);
	reverse(a+1,a+n+1);
	int l=1,r=n,ans=-1;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(pd(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	cout << ans;
	return 0;
}

Python3(3.5.2) 解法, 执行用时: 1467ms, 内存消耗: 27348K, 提交时间: 2020-07-16 19:40:36

def core(a,k):
    l,r=0,len(a)
    a.sort(reverse=True)
    while l<r:
        mid=(l+r)//2
        if find(a,mid,k):
            r=mid
        else:
            l=mid+1
    return l

def find(a,t,k):
    if t==0:
        return False
    res=0
    for i in range(len(a)):
        res+=max(0,a[i]-i//t)
    if res>=k:
        return True
m,n=map(int,input().split())
a=list(map(int,input().split()))
print(core(a,n))

上一题