jzoj1298. 牛棚

2024-01-30 08:32
文章标签 牛棚 jzoj1298

本文主要是介绍jzoj1298. 牛棚,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

jzoj1298. 牛棚

  • 题目
    • Description
      • 译题:
      • 原题:
    • Input
    • Output
    • Sample Input
    • Sample Output
    • Hint
  • 分析
  • CODE

题目

Description

译题:

FJ有N(2<=N<=1,500)头牛编号为1到N,FJ新盖了S(N<=S<=1,000,000)个牛棚,编号为1到S,S个牛棚排成一排,相邻牛棚距离为1。
每个牛棚只能住一头牛,每头牛都选择了一个牛棚P_i来休息,当两头牛离得太近时就会变得很暴躁,FJ想移动一些牛到其他牛棚使得他们之间的间距尽可能大,同时FJ又希望这N-1个间距尽可能相似。
具体一点说,FJ希望所有间距与(S-1)DIV(N-1)最多相差1,而且希望这N-1个间距尽可能多的等于(S-1)DIV(N-1)。例如4个牛住8个牛棚,可以有以下方案:1,3,5,8或1,3,6,8,但1,2,4,7或1,2,4,8是不符合要求的。
帮助FJ用最少的移动距离满足要求。

原题:

Farmer John has N (2 <= N <= 1,500) prize milk cows conveniently numbered 1…N. His newly-painted barn has S (N <= S <= 1,000,000) stalls (conveniently numbered 1…S) in a single long line; each stall is a unit distance from its neighboring stall(s).

The cows have made their way to the stalls for a rest; cow i is in stall P_i. Antisocial as they are, the cows get grumpy if they are situated in stalls very close to each other, so Farmer John wants to move the cows to be as spread out as possible.

FJ wants to make sure that the N - 1 distances between adjacent cows are as large as possible, and he would also like them to be similar to each other (i.e., close to equi-distant spacing).

In particular, FJ would like all distances between adjacent cows to be at most 1 different from (S - 1) / (N - 1), where integer division is used. Moreover, he would like as many of these distances as possible to be exactly equal to (S - 1) / (N - 1) [integer division]. Thus, with four cows and eight stalls, one can place the cows at positions 1, 3, 5, 8 or 1, 3, 6, 8 but not at 1, 2, 4, 7 or 1, 2, 4, 8.

Help FJ spread the cows as efficiently as possible by calculating and reporting the minimum total distance that the cows have to move in order to achieve proper spacing. Ignore the distance it takes for a cow to enter or exit a stall.

Input

  • Line 1: Two space-separated integers: N and S

  • Lines 2…N+1: Line i+1 contains the single integer: P_i

第1行:两个空格隔开的整数N和S
  第2到N+1行:第i+1行包含一个整数P_i

Output

  • Line 1: A single integer: the minimum total distance the cows have to travel. This number is guaranteed to be under 1,000,000,000 (thus fitting easily into a signed 32-bit integer).
      输出一个整数表示最少移动距离。

Sample Input

5 10
2
8
1
3
9

Sample Output

4

Hint

在这里插入图片描述

分析

dp
状态转移方程:
f[i][j]=min(f[i-1][j-1],f[i-1][j])+abs(a[i]-i*x+x-j-1);

CODE

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;int n,s,a[2000],f[2000][2000];bool cmp(int a,int b){return a<b;
}int main(){freopen("gwraze2.in","r",stdin);freopen("graze2.out","w",stdout);scanf("%d%d",&n,&s);for (int i=1;i<=n;i++)scanf("%d",&a[i]);sort(a+1,a+n+1,cmp);memset(f,0x3f3f3f,sizeof(f));f[1][0]=a[1]-1;int x=(s-1)/(n-1);int y=(s-1)%(n-1);for (int i=2;i<=n;i++){s=min(i-1,y); f[i][0]=f[i-1][0]+abs(a[i]-i*x+x-1);for (int j=1;j<=s;j++)f[i][j]=min(f[i-1][j-1],f[i-1][j])+abs(a[i]-i*x+x-j-1);}printf("%d\n",f[n][y]);return 0;
}

这篇关于jzoj1298. 牛棚的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/659662

相关文章

【AcWing】蓝桥杯集训每日一题Day32|贪心|1349.修理牛棚

1349.修理牛棚 1349. 修理牛棚 - AcWing题库难度:中等时/空限制:1s / 64MB总通过数:1275总尝试数:2405来源:usaco training 1.4算法标签贪心 题目内容 在一个下着暴风雨的夜晚,大风掀翻了农夫约翰的牛棚的屋顶和大门。 牛棚一个个的并排排成一排,奶牛就住在牛棚中过夜。 由于一些奶牛正在外面度假,牛棚并没有住满,有的牛棚住着牛,有的牛棚空着。

【单调队列单调栈专题】【蓝桥杯备考训练】:矩形牛棚、单调栈、滑动窗口、子矩阵、最大子序和、烽火传递【已更新完成】

目录 1、矩形牛棚(usaco training 6.1) 思路: 预处理的过程: 判断左右边界的过程: 代码: 2、单调栈(单调栈模板) 思路: 基本步骤: 1、维护单调性 2、处理要求的操作 3、入栈 代码: 3、滑动窗口(单调队列模板) 思路: 基本步骤(以求最大值为例): 1、维护单调性(在尾部做处理) 2、入队 3、判断是否滑出窗口,滑出则hh++ 4、做要求的处理 代码: 4、子矩阵

1672: [Usaco2005 Dec]Cleaning Shifts 清理牛棚

考虑令f[i]表示至少把前i个点打扫了所需要的最小花费, 那么对于第i个奶牛打扫的即为f[a[i].e] = min(f[a[i].s-1]+a[i].w); 考虑更新了f[a[i].e]实际上也对于前a[i].e个点均有影响,所以还需对f[j]取min j < a[i].e 知道树状数组是可以维护前缀最小值的,那么反转区间,随便维护即可。 c++代码如下: #include<bits/

动态规划——悬线法 (P1169 棋盘制作 p4147 玉蟾宫 p2701 巨大的牛棚 p1387 最大正方形)

学习于luogu p1169 第一篇题解 悬线法 用途:        解决给定矩阵中满足各种条件的最大子矩阵 做法:   用一条线(横竖貌似都行)左右移动直到不满足约束条件或者到达边界 定义数组:   le[i][j]: 代表从(i,j)能到达的最左位置   ri[i][j]: 代表从(i,j)能到达的最右位置   up[i][j]: 代表从(i,j)向上扩展最长长度. 预处

【物联网应用案例】牧场牛棚环境管理项目

众所周知,奶牛的健康和牛奶的产量在很大程度上取决于其所在的环境。对于牧场而言,牛棚内的环境更是至关重要。一个适宜的环境不仅能保证奶牛的舒适度,还能提高其产奶量,从而为牧场带来更多的经济效益。 为了更好地理解牛棚环境对奶牛健康和牛奶产量的影响,首先需要深入了解奶牛的生理特点和生活习性。奶牛作为哺乳动物,对环境温度、湿度、通风和光照等条件非常敏感。在适宜的环境下,奶牛能够保持良好的生理状态,进而提高

USACO——修理牛棚

洛谷 P1209 [USACO1.3]修理牛棚 Barn Repair 题目描述 在一个夜黑风高,下着暴风雨的夜晚,farmer John的牛棚的屋顶、门被吹飞了。 好在许多牛正在度假,所以牛棚没有住满。 牛棚一个紧挨着另一个被排成一行,牛就住在里面过夜。 有些牛棚里有牛,有些没有。 所有的牛棚有相同的宽度。 自门遗失以后,farmer John必须尽快在牛棚之前竖立起新的木板。 他的新木材供

[BZOJ1651] [Usaco2006 Feb]Stall Reservations 专用牛棚

传送门 http://www.lydsy.com/JudgeOnline/problem.php?id=1651 题目大意 给出奶牛运动的时间段,询问同一时间最多的奶牛数 题解 线段树或差分序列 线段树 varx:array[0..3000000,1..4]of longint;i,j,k:longint;n,a,b,m:longint;function max(a,b:longi

AOJ890 修理牛棚 【贪心】

题面: Description 在一个夜黑风高,下着暴风雨的夜晚,农民约翰的牛棚的屋顶、门被吹飞了。 好在许多牛正在度假,所以牛棚没有住满。 剩下的牛一个紧挨着另一个被排成一行来过夜。 有些牛棚里有牛,有些没有。 所有的牛棚有相同的宽度。 自门遗失以后,农民约翰必须尽快在牛棚之前竖立起新的木板。 他的新木材供应商将会供应他任何他想要的长度,但是供应商只能提供有限数目的木板。 农民约翰想将他购买

AcWing第 127 场周赛 - AcWing 5283. 牛棚入住+AcWing 5284. 构造矩阵 - 模拟+快速幂+数学

AcWing 5283. 牛棚入住 题目数据范围不大,直接暴力模拟即可 按照题目所说的意思即可。 #include <math.h>#include <stdio.h>#include <algorithm>#include <cstring>#include <iostream>using namespace std;const int N = 1e5 + 10;#define

acwing 5283. 牛棚入住

题目 - 点击直达 1. 5283. 牛棚入住1. 题目详情1. 原题链接2. 题目要求3. 基础框架 2. 解题思路1. 思路分析2. 时间复杂度3. 代码实现 1. 5283. 牛棚入住 1. 题目详情 贝茜经营的牛棚旅店中有 a 个可供一头牛入住的小牛栏和 b 个可供两头牛入住的大牛栏。 初始时,所有牛栏都是空的。 已知,今天一共有 n 波奶牛依次前来入住,每波由