多校第二场 1004 hdu 5303 Delicious Apples(背包+贪心)
2024-08-28 20:32:48
题目链接:
题目大意:
在一个周长为L的环上。给出n棵苹果树。苹果树的位置是xi,苹果树是ai,苹果商店在0位置,人的篮子最大容量为k,问最少做多远的距离可以把苹果都运到店里
题目分析:
首先我们能够(ˇˍˇ) 想~,假设在走半圆之内能够装满,那么一定优于绕一圈回到起点。所以我们从中点将这个圈劈开。那么对于每一个区间由于苹果数非常少,所以能够利用belong[x]数组记录每一个苹果所在的苹果树位置,然后将苹果依照所在的位置排序,那么也就是我们知道每次拿k个苹果的代价是苹果所在的最远的位置。
所以我们记录。sum[i]就是拿第i个苹果的时候的最小代价和,利用背包的思想就是
sum[i] = sum[i-k] + d[i]
if ( i <= k )
sum[i] = d[i]
由于当最后苹果数不足k个时候。能够通过绕一圈拿走全部的苹果。所以说。最后要枚举左右这一圈拿走的苹果,然后算取最大的情况。详细看代码。有不懂的能够再评论中询问
代码例如以下:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
#define MAX 100007 using namespace std; typedef long long LL;
int t,l,n,k;
LL sum1[MAX];
LL sum2[MAX];
LL belong[MAX];
vector<int> b1;
vector<int> b2; int main ( )
{
scanf ( "%d" , &t );
while ( t-- )
{
scanf ( "%d%d%d" , &l , &n , &k );
int m = 0;
int x,a;
b1.clear();
b2.clear();
for ( int i = 0; i < n ; i++ )
{
scanf ( "%d%d" , &x , &a );
for ( int i = 0 ; i < a ; i++ )
belong[++m] = x;
}
k = min ( k , m );
for ( int i = 1 ; i <= m ; i++ )
{
//cout << belong[i] << " ";
if ( belong[i]*2 >= l ) b2.push_back ( l-belong[i] );
else b1.push_back( belong[i] );
}
//cout << endl;
sort ( b1.begin() , b1.end() );
sort ( b2.begin() , b2.end() );
int len1 = b1.size();
sum1[0] = sum2[0] = 0;
for ( int i = 0 ; i < len1 ; i++ )
{
int id = i+1;
if ( id <= k ) sum1[id] = b1[i];
else sum1[id] = b1[i] + sum1[id-k];
}
int len2 = b2.size();
//cout << len1 << " " << len2 << endl;
for ( int i = 0 ; i < len2 ; i++ )
{
int id = i+1;
if ( id <= k ) sum2[id] = b2[i];
else sum2[id] = b2[i] + sum2[id-k];
}
LL ans = ( sum1[len1] + sum2[len2] )*2 ;
for ( int i = 0 ; i <= len1 && i<= k; i++ )
{
int m1 = len1 - i ;
int m2 = ( 0 , len2 - (k-i) );
ans = min ( ans , 2*(sum1[m1]+sum2[m2])+l );
}
printf ( "%I64d\n" , ans );
}
}
最新文章
- Makefile隐含规则
- SQL语法的重要知识点总结
- javax.servlet.ServletException: com.microsoft.jdbc.base.BaseDatabaseMetaData.supportsGetGeneratedKeys()Z
- sql表设计器的几个默认值
- HDU 1532 Drainage Ditches 最大流 (Edmonds_Karp)
- jQuery 数据滚动(上下)
- vue单页页面开发教程及注意事项
- spark、standalone集群 (2)集群zookeeper 热备
- include的作用
- [C] 在 C 语言编程中实现动态数组对象
- How to diagnose vehicle fault code by BMW ICOM and ISTA-D software
- iOS.AutomatePackageBuild.0-Resource-List
- P1231 教辅的组成
- [javaSE] 数组(获取最值)
- mac 下 outlook 邮箱 服务器端口设置
- Java特性之继承的应用
- 51nod1031 骨牌覆盖 组合数学
- Scikit-learn方法使用总结
- JavaScript初识(二)
- HrrpClient使用