题目：http://codeforces.com/problemset/problem/746/F
先感叹一下题目之长！
一些测试样例在后面给出。
题目大意：
Sasha 去工作的路上喜欢听歌，途中经历 K 分钟，有一个歌单，顺序播放。
每首歌都对应一个开心值 ai ，持续时间为 ti 分钟
开始的时候先选定一首歌曲，例如第x首，从这首歌开始顺序播放，终止条件为：歌单播放完或行程到终点了
一首歌可以播放整首或只播放一部分，后者必须播放歌曲的一半时间（取上整）以上才能获得对应的开心值。
播放一部分还有一个曲目数量限制为w，只有w首歌曲支持半曲播放。
问：确定n w k 的情况下，Sasha能够获取的最大开心值。
思路：
设定两个set 容器，一个存整首曲目，一个存半曲曲目。想要在固定的时间K 之内听更多的歌曲开心值更高，而且必须是连续的曲目，那就要把时间长的尽量折半，把时间短的让出来按整首去听。所以，刚开始都先把歌曲按半曲存，如果半曲列表满了之后，再根据情况选择性弹出，替换。当K 时间用完之后，就从左边开始删歌曲，保证后面遍历完所有的情况，因为，可以从中任何一首歌曲开始听。这样求取过程中产生的最大开心值即可。半曲列表最大容量为w，原来用的加法做，感觉有点复杂，后来改了减法，这个看个人喜好。
代码如下：
#include<iostream>
#include<cstdio>
#include<set>
using namespace std;
int arr[];
int happy[]; inline long max(long x, long y)
{
return x > y ? x : y;
} int main()
{
long N, W, K;
while (scanf("%ld %ld %ld", &N, &W, &K) != EOF)
{
long result = , RESULT = ;
set<pair<int, int> >S_, S; //分别代表半曲容器和整首容器
for (int i = ; i <= N; ++i)
scanf("%d", happy + i);
for (int i = ; i <= N; ++i)
scanf("%d", arr + i);
int l, r;
l = r = ;
while (r <= N)
{
//right pointer;
while (r <= N)
{
if (W)
{
if (K >= (arr[r] + ) / )
{
K -= (arr[r] + ) / ;
RESULT = max(RESULT, result += happy[r]);
S_.insert(make_pair(arr[r], r));
r++;
W--;
}
else break; //行程结束
}
else //如果w位置已满
{
int tmp = S_.begin()->first;
if (tmp <= arr[r] && K >= (arr[r] + ) / - (tmp + ) / + tmp) //如果当前的比半曲列表中时间最短的花费时间长，替换
{
K -= (arr[r] + ) / - (tmp + ) / + tmp;
RESULT = max(RESULT, result += happy[r]);
auto p = S_.begin();
S.insert(*p);
S_.erase(p);
S_.insert(make_pair(arr[r], r));
r++;
}
else if (tmp > arr[r] && K >= arr[r]) //如果当前的比半曲列表中时间最短的还短，那么就把当前的短歌放入S
{
K -= arr[r];
RESULT = max(RESULT, result += happy[r]);
S.insert(make_pair(arr[r], r));
r++;
}
else break;
}
}
//left pointer; K时间已经满了，从左边开始删除歌曲，以保证继续往后遍历
if (l < r)
{
if (S.find(make_pair(arr[l], l)) != S.end())
{
K += arr[l];
result -= happy[l];
S.erase(make_pair(arr[l], l));
}
else
{
K += (arr[l] + ) / ;
result -= happy[l];
S_.erase(make_pair(arr[l], l));
W++;
if (!S.empty())
{
auto p = --S.end();
K += p->first - (p->first + ) / ;
S_.insert(*p);
W--;
S.erase(p);
}
}
l++;
}
else l++, r++;
}
printf("%d\n", RESULT);
}
}
Sample Input
Sample Output
感谢您的阅读，生活愉快~