思维题。
考虑y坐标,简单的货舱选址问题,选择中位数即可。
再考虑x坐标,由于直接研究布置方法非常困难,可以倒着想:不管如何移动,最后的坐标总是相邻的,且根据贪心的思路,站队前后士兵的相对位置应该不变。那么记\(pos\)为最后水平线起点的前一位置,则有\(x_1-1=pos,x_2-2=pos,…,x_n-n=pos\),所以答案为\(\sum_{i=1}^{n}|(x_i-i)-k|\),这样就又变成了一道中位数的题目。
不放代码了。
贪心(其实严格来讲是一道DP题
求最大子矩阵之和,考虑将它转化为最大子段和问题,我们可以对于每一列枚举所有的\(i,j\)(即加起来不同的情况),然后这样把每一列变成一个数,拿做最大字段和的方法来求解即可。
复杂度\(O(n^3)\)。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,a[105][105],t[105],sum,ans=-0x3f3f3f3f;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;++i)
{
memset(t,0,sizeof(t));
for(int j=i;j<=n;++j)
{
sum=0;
for(int k=1;k<=n;++k)
{
sum+=t[k]+=a[j][k]; //注意这里先枚举j再枚举k,所以此时t[k]已经包含之前算过的值了(考虑前缀和
ans=max(ans,sum);
if(sum<0) sum=0;
}
}
}
printf("%d",ans);
return 0;
}
其实这题应该思考一下就能想出来了……(才怪
考虑x与y对利润的贡献,可以发现题目的数据范围保证了贪心算法的正确性——x远大于y对利润的贡献,所以考虑对任务按x从大到小排序,对每个任务选出满足条件且y值最小的机器。
证明的话……一般不会说显然就完事了,不过也可以明天上课的时候推一下
#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
int n,m,cnt;
long long ans;
struct P{int x,y;}a[100005],b[100005];
multiset<int> s;
bool cmp(P x,P y) {return x.x==y.x?x.y<y.y:x.x<y.x;}
int main()
{
while(~scanf("%d%d",&n,&m))
{
s.clear(); cnt=ans=0;
for(int i=1;i<=n;++i) scanf("%d%d",&a[i].x,&a[i].y);
for(int i=1;i<=m;++i) scanf("%d%d",&b[i].x,&b[i].y);
sort(a+1,a+n+1,cmp); sort(b+1,b+m+1,cmp);
for(int i=m,j=n;i;--i)
{
while(j && a[j].x>=b[i].x) s.insert(a[j--].y);
multiset<int>::iterator it=s.lower_bound(b[i].y);
if(it!=s.end())
{
cnt++; ans+=b[i].x*500+b[i].y*2;
s.erase(it);
}
}
printf("%d %lld\n",cnt,ans);
}
return 0;
}
继续加油啊……
手机扫一扫
移动阅读更方便
你可能感兴趣的文章