死亡
【问题描述】
现在有个位置可以打sif，有个人在排队等着打sif。现在告诉你前个人每个人需要多长的时间打sif，问你第个人什么时候才能打sif。（前个人必须按照顺序来）
【输入格式】
第一行两个整数如上所述。
接下来行每行一个整数代表每个人所需要用的时间。
【输出格式】
一行一个整数表示答案。
【样例输入】
3 2
1
1
1
【样例输出】
1
【样例解释】
山里有座庙。
【数据规模与约定】
对于的100%数据，每个人所需用的时间不超过10^5。
|
测试点 |
测试点 |
||||
|
1 |
10 |
10 |
1 |
5000 |
500 |
|
2 |
20 |
10 |
2 |
100000 |
5000 |
|
3 |
50 |
10 |
3 |
100000 |
10000 |
|
4 |
1000 |
500 |
4 |
100000 |
20000 |
|
5 |
2000 |
500 |
5 |
100000 |
50000 |
题解：用一个优先队列轻松解决。由于优先队列由大到小排列，因此可以将时间的相反数压入队列，每次取栈顶元素。
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#define N 100100
using namespace std; int n,m;
int t[N];
long long ans;
priority_queue<long long> q;
int main()
{
freopen("death.in","r",stdin);
freopen("death.out","w",stdout); scanf("%d%d",&n,&m);
for (int i=;i<=n;i++) scanf("%d",&t[i]);
for (int i=;i<=m;i++)
q.push();
for (int i=;i<=n;i++)
{
long long k=q.top();
q.pop();
k=-k;
k+=t[i];
k=-k;
q.push(k);//取相反数压入栈中
}
ans=-q.top();
cout<<ans<<endl; fclose(stdin);
fclose(stdout); return ;
}
优先队列
凝视
【问题描述】
背包是个好东西，希望我也有。
给你一个二维的背包，它的体积是。现在你有一些大小为和的物品，每个物品有自己的价值。你希望往背包里面装一些物品，使得它们的价值和最大，问最大的价值和是多少。
【输入格式】
第一行一个整数代表该测试点的数据组数。
对于每组数据，第一行有四个整数，其中分别代表大小为和大小为的物品个数。
接下来一行有个数代表每个物品的价值。
接下来一行有个数代表每个物品的价值。
【输出格式】
对于每组询问，输出能够达到的价值最大值。
【样例输入】
1
2 3 2 2
1 2
1 2
【样例输出】
4
【样例解释】
庙里有座山。
【数据规模与约定】
对于20%的数据，N,M<=10.n1,n2<=100.
对于70%的数据，N,M<=100.n1,n2<=2000.
对于100%的数据，1<=T<=10,1<=N,M<=500.n1,n2<=10000.
题解：由于能装上1*3的物品，那么一定能装上1*2的物品。因此可以枚举1*3的物品，然后根据它剩下的体积装1*2的物品。找到最大价值。如果全部装1*3的物品，那么剩下的体积为1或者2，但有一种特殊情况需要考虑。注意当n==2或m==2是，若此时n%3==2&&m%3==2,那么剩下的4体积无法装入1*3的物品。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<ctime>
#include<queue>
#define N 10100
using namespace std;
int t,n,m,n1,n2,k,ans();
int a1[N]={},a2[N]={};
bool cmp(int x,int y)
{
return (x>y);
}
int main()
{
freopen("eyesight.in","r",stdin);
freopen("eyesight.out","w",stdout);
scanf("%d",&t);
while (t--)
{ scanf("%d%d%d%d",&n,&m,&n1,&n2);
a1[]=a2[]=;
for (int i=;i<=n1;i++) scanf("%d",&a1[i]);
for (int i=;i<=n2;i++) scanf("%d",&a2[i]);
sort(a1+,a1++n1,cmp);
sort(a2+,a2++n2,cmp);
for (int i=;i<=n1;i++) a1[i]+=a1[i-];
for (int i=;i<=n2;i++) a2[i]+=a2[i-];
if ((n%==)&&(m%==)&&(n==||m==)) k=;
else k=n*m%;
ans=;
n2=min(n2,(n*m-k)/);
for (int i=;i<=n2;i++)
ans=max(ans,a2[i]+a1[min(n1,(n*m-i*)/)]);
cout<<ans<<endl;
} fclose(stdin);
fclose(stdout); return ;
}
贪心