NC205055. 牛牛爱学习
描述
输入描述
第一行输入一个n(1≤n≤106)和m(1≤m≤109),第二行输入每本书的知识值ai(0≤ai≤109)。
输出描述
输出最少要多少天才能获得大于等于m点的知识力,如果无法获得,请输出-1。
示例1
输入:
4 10 4 4 4 4
输出:
1
说明:
示例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))