NC21613. 牛牛的战役
描述
再给你一个数组b
再给你一个数组c
c[i]表示敌方b[i]战斗力的人有c[i]个
每个oier每次可以选择一名敌方人员进行战斗，如果战斗力大于等于敌方人员，就可以战胜，经验值+1
最开始的时候每个人的经验值都是0
现在牛牛想要打败所有敌方人员，也就是说每个敌方人员都要被一个oier所打败
但是牛牛想要最小化最大的经验值
如果不能打败所有的敌方人员，输出-1
否则输出最小化最大的经验值
输入描述
第一行输入一个整数n表示我方人员的数量(1 ≤ n ≤ 50)
第二行输入 n个整数ai表示我方每个人员的战斗力(1 ≤ ai ≤ 10000)
第三行输入一个整数m表示b数组的长度(1 ≤ m ≤ 50)
第四行输入m个整数bi (1 ≤ bi ≤ 10000)
第五行输入m个整数ci (1 ≤ ci ≤ 1014)
输出描述
输出一个整数
示例1
输入:
3 2 3 5 3 1 3 4 2 9 4
输出:
7
说明:
牛牛指挥0号oier击败2个战斗力为1的敌方人员示例2
输入:
3 2 3 5 3 1 1 2 2 9 4
输出:
5
示例3
输入:
3 14 6 22 2 8 33 9 1
输出:
-1
示例4
输入:
1 1 20 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000 100000000000000
输出:
2000000000000000
C++14(g++5.4) 解法, 执行用时: 13ms, 内存消耗: 632K, 提交时间: 2020-05-19 17:03:16
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int a[55];
struct Node {
int b;
ll c;
bool operator < (Node& n) {
return b < n.b;
}
}b[55];
int main(){
int n, m;
cin >> n;
for (int i = 1; i <= n; i++)cin >> a[i];
cin >> m;
for (int i = 1; i <= m; i++)cin >> b[i].b;
for (int i = 1; i <= m; i++)cin >> b[i].c;
sort(a + 1, a + 1 + n);
sort(b + 1, b + 1 + m);
if (b[m].b > a[n])cout << "-1" << endl;
else {
ll sum = 0, ans =0;
for (int i = m; i >= 1; i--) {
sum += b[i].c;
int temp = n+1-(lower_bound(a + 1, a + 1 + n, b[i].b) - a);
if (sum % temp == 0) {
ans = max(ans, sum / temp);
}
else {
ans = max(ans, sum / temp + 1);
}
}
cout << ans << endl;
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 632K, 提交时间: 2020-03-07 19:11:33
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node
{
int b;
ll c;
}t[55];
bool cmp(node x,node y)
{
return x.b<y.b;
}
int main()
{
int a[55],n,m;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
cin>>m;
for(int i=1;i<=m;i++)
cin>>t[i].b;
for(int i=1;i<=m;i++)
cin>>t[i].c;
sort(a+1,a+1+n);
sort(t+1,t+1+m,cmp);
ll sum=0,s,best=-1;
if(a[n]<t[m].b)
cout<<"-1"<<endl;
else
{
for(int i=m;i>=1;i--)
{
sum=sum+t[i].c;
s=n+1-(lower_bound(a+1,a+1+n,t[i].b)-a);
if(sum%s==0)
best=max(best,sum/s);
else
best=max(best,(sum/s+1));
}
cout<<best<<endl;
}
return 0;
}