NC21195. Kuangyeye and hamburgers
描述
输入描述
the first line of input contains two integer n and k--the number of hamburgers on the counter and the number of plans Kuangyeye had;
the next line contains n integer--the i-th integer represents the weight of i-th hamburger,namely wi;
Each the following k line contains two integer ai and bi ,represents Kuangyeye's strategy in his i-th plan.
输出描述
Output contain a single integer,represents maximum weight of hamburgers Kuangyeye can eat.
示例1
输入:
5 2 4 3 5 2 6 1 1 3 4
输出:
7
说明:
Kuangyeye's first plan was to eat the hamburger weighing 6；C++14(g++5.4) 解法, 执行用时: 76ms, 内存消耗: 1236K, 提交时间: 2019-01-06 14:56:25
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int a[maxn],sum[maxn],n;
int main()
{
int k,aa,b,ans=0;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+a[i];
while(k--)
{
scanf("%d%d",&aa,&b);
aa=n-aa+1,b=n-b+1;
ans=max(ans,sum[aa]-sum[b-1]);
}
printf("%d\n",ans);
}
C++ 解法, 执行用时: 28ms, 内存消耗: 820K, 提交时间: 2021-09-08 19:39:28
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1,greater<int>());
for(int i=1;i<=n;i++) a[i]+=a[i-1];
int maxx=0;
while(k--)
{
int x,y;
scanf("%d%d",&x,&y);
maxx=max(maxx,a[y]-a[x-1]);
}
cout<<maxx<<endl;
}
pypy3 解法, 执行用时: 508ms, 内存消耗: 34432K, 提交时间: 2022-06-28 19:30:29
n,k=map(int,input().split())
res = []
res.append(0)
l = [*map(int,input().split())]
l.sort()
l.reverse()
res += l
for _ in range(1,n+1) :
res[_] += res[_-1]
ans = -1e18
for _ in range(k) :
l,r=map(int,input().split())
ans = max(ans,res[r]-res[l-1])
print(ans)