Once edited 2 年，10 月前
Just simulate the described process. Maintain the number of non-space characters on your current line (denoted by w in the code below). If adding the next word would cause the number of non-space characters to exceed K, then place it on a new line.
Instead of trying to think about the problem in terms of minimizing the amount of time needed to accomplish a certain distance, we can flip the problem around - if Bessie can run for T seconds and she wants to be running no more than X meters per second at the end of the T seconds, what is the furthest distance she can run?
Intuitively, we want her speed to be as high as possible throughout her run. If there were no speed cap at the end, Bessie would consistently increase her speed every second. Because of the presence of the speed cap though, Bessie may need to switch from speeding up to slowing down in order to meet the requirement of traveling no more than X meters per second at the end.
As a result, for a given speed V, Bessie will be traveling at that speed for at most 2 seconds - 1 second when she is speeding up, and one second when she is slowing down. We can therefore simulate Bessie’s fastest possible run subject to her starting at 0 meters per second and ending with speed no more than X meters per second as follows - we will track Bessie’s distance traveled while she is speeding up and while she is slowing down. We will increment Bessie’s speed starting at 1 meter per second until she has traveled enough distance to finish the race. Increment Bessie’s distance covered while speeding up by this speed, and check if Bessie’s total distance traveled exceeds K meters. If the distance has not been exceeded, and Bessie could travel at this speed while slowing down, then increment Bessie’s distance covered while slowing down by this speed, and perform the total distance check again.
The moment in time when Bessie’s theoretical maximum distance traveled exceeds K meters is the desired answer. It is worth noting that following this specific strategy of speeding up and slowing down may not actually meet the race conditions properly, but it is always possible to construct a strategy that covers exactly the given distance in the asserted time.
There is one final concern - is simulating this one second at a time fast enough? The worst possible case here is where Bessie needs to run $10^9$ meters and she must end the race running at 1 meter per second. In this case, it takes 63245 seconds. Performing one thousand of these simulations should therefore run in time comfortably.
#include <stdio.h>
int solve(int dist) {
int minspeed;
scanf("%d", &minspeed);
int lhstravel = 0;
int rhstravel = 0;
int timeused = 0;
for(int currspeed = 1;; currspeed++) {
lhstravel += currspeed;
timeused++;
if(lhstravel + rhstravel >= dist) return timeused;
if(currspeed >= minspeed) {
rhstravel += currspeed;
timeused++;
if(lhstravel + rhstravel >= dist) return timeused;
}
}
}
int main() {
int k, n;
scanf("%d %d", &k, &n);
for(int i = 0; i < n; i++) {
printf("%d\n", solve(k));
}
}
Small $K$:
After sorting the trees in decreasing order of $B_i$, we don't need to consider trees outside of the first $K.$ Furthermore, if we decide to select $b>0$ baskets from tree $i,$ then each basket should have either $\left\lfloor \frac{B_i}{b}\right\rfloor$ or $\left\lfloor \frac{B_i}{b}\right\rfloor+1$ berries. Using these observations, we can do some sort of backtracking.
Full Solution:
Let $b$ the minimum number of berries in one of the buckets that Elsie receives. Without loss of generality, we can assume that all of Elsie's buckets contain exactly $b$ berries. Now our goal is to maximize the number of berries placed into $K$ buckets of size at most $b$ such that at least $\frac{K}{2}$ buckets have exactly $b$ berries inside. Consider a single tree's allotment into the buckets in an optimal solution. There’s no point having multiple buckets with less than $b$ berries from this
tree. So all buckets will have exactly $b$ berries aside from at most one.
Thus, it’s clearly optimal to repeatedly fill buckets of size exactly $b$ until we run out of buckets or all trees have less than $b$ berries remaining. If we still have buckets to fill, sort the remaining trees by $B_i\pmod{b}$ and iterate from the largest to the smallest value. We can repeat this procedure for each $b=0\ldots \max(B_i),$ which runs in $O(\max(B_i)\cdot N\log N)$ time.
#include <iostream>
#include <algorithm>
using namespace std;
int N,K;
int A[100000];
int mod;
bool cmp(int a,int b)
{
return (a%mod) > (b%mod);
}
int main()
{
freopen("berries.in","r",stdin);
freopen("berries.out","w",stdout);
cin >> N >> K;
int M = 0;
for(int i=0;i<N;i++)
{
cin >> A[i];
M = max(M, A[i]);
}
int best = 0;
for(int b=1;b <= M;b++)
{
int full = 0;
for(int i=0;i<N;i++)
full += A[i]/b;
if(full < K/2)
break;
if(full >= K)
{
best = max(best, b*(K/2));
continue;
}
mod = b;
sort(A, A+N, cmp);
int cur = b*(full - K/2);
for(int i=0;i<N && i+full<K;i++)
cur += A[i]%b;
best = max(best,cur);
}
cout << best << '\n';
}
If Bessie travels for exactly $t$ days then the amount of moonies that she makes is bounded above by $1000t-t^2,$ which is negative when $t>1000.$ Thus, it suffices to keep track of the DP states $dp[x][t]$ for each $1\le x\le N, 0\le t\le 1000,$ denoting the maximum amount of moonies Bessie can make up to time $t$ if she is located at city $x$ at time $t$. The final answer will be $\max_{0\le t\le 1000}(dp[1][t]-Ct^2).$ This solution runs in $O(\max(m_i)\cdot (N+M)).$ time.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
const int MAXT = 1005;
long long n, m, c;
long long value[MAXN];
long long dp[2][MAXN];
vector<pair<int, int>> edges;
int main() {
freopen("time.in","r",stdin);
freopen("time.out","w",stdout);
cin >> n >> m >> c;
for (int i = 1; i <= n; i++) {
cin >> value[i];
}
int a, b;
for (int i = 0; i < m; i++) {
cin >> a >> b;
edges.push_back(make_pair(a, b));
}
long long max_profit = 0;
memset(dp, -1, sizeof dp);
dp[0][1] = 0;
for (int t = 1; t < MAXT; t++) {
int p = t % 2;
memset(dp[p], -1, sizeof dp[p]);
for (auto& e : edges) {
a = e.first;
b = e.second;
if (dp[1-p][a] >= 0) {
dp[p][b] = max(dp[p][b], dp[1-p][a] + value[b]);
}
}
max_profit = max(max_profit, dp[p][1] - c * t * t);
}
cout << max_profit << "\n";
}
对于一个给定的区间$[l, r]$，怎样操作才是最优的呢？
显然我们不会对一个数操作两次．设倒数第$i$次操作中选中的数为$A_i$，那么最终得到的水量为$V$为：
$$V = \sum_{i = 1}^{r - l + 1} \frac{A_i}{2^i}$$
因此我们一定会把水量较多的留到最后操作，那么我们只需要区间内排个序统计就可以算出答案，暴力是$O(n^3\log n)$的．
注意到题目输出实数，对于上式中较大的$i$，$\frac{A_i}{2^i}$可以忽略不计．
这样我们只需要找到一个区间内最大的大约$T = 50$个数就可以了，在固定左端点的情况下向右移动右端点，并维护最大的$T$个数即可．$O(n^2T)$
考虑分开计算每个数的贡献，对于第$i$个数和一个区间$[l, r]$，这个数的贡献只与这个区间内比它大的数的个数$t$有关．与上面类似的，当$t > T$时，贡献可以忽略不计．
于是我们在$i$的左边和右边分别找$T$个离$i$尽量近且比$w_i$大的数，假设左边找到的数的位置从右往左是$l_1, l_2, …, l_T$，右边从左往右是$r_1, r_2, …, r_T$，方便起见$l_0 = r_0 = i$. 则$i$的贡献$sum_i$可以估算为：
$$\begin{aligned}sum_i &= w_i \times \sum_{u = 1}^T \sum_{v = 1}^T (l_{u-1} - l_u) \times (r_v - r_{v-1}) \times \frac{1}{2^{u + v - 1}} \
&= 2w_i (\sum_{u=1}^T \frac{l_{u-1} - l_u}{2^u}) (\sum_{v=1}^T \frac{r_v - r_{v-1}}{2^v})
\end{aligned}$$
现在唯一的问题是找到最近的$T$个大于$w_i$的数，一种高效的方法是按数从小到大的顺序计算贡献，用链表维护比当前数大的数．计算完一个数的贡献后，将它从链表中删去.
复杂度为$O(nT + n\log n)$