Delicious Apples

Time Limit: 5000/3000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)

Total Submission(s): 199 Accepted Submission(s): 54

Problem Description

There are

n apple trees planted along a cyclic road, which is

L metres long. Your storehouse is built at position

0 on that cyclic road.

The

ith tree is planted at position

xi, clockwise from position

0. There are

ai delicious apple(s) on the

ith tree.

You only have a basket which can contain at most

K apple(s). You are to start from your storehouse, pick all the apples and carry them back to your storehouse using your basket. What is your minimum distance travelled?

1≤n,k≤105,ai≥1,a1+a2+...+an≤105

1≤L≤109

0≤x[i]≤L

There are less than 20 huge testcases, and less than 500 small testcases.

Input

First line:

t, the number of testcases.

Then

t testcases follow. In each testcase:

First line contains three integers,

L,n,K.

n lines, each line contains

xi,ai.

Output

Output total distance in a line for each testcase.

Sample Input

2 10 3 2 2 2 8 2 5 1 10 4 1 2 2 8 2 5 1 0 10000

Sample Output

18 26

Source

题目链接：

题目大意：有一个长为L的环。n个苹果树，一个篮子最多装k个苹果，装完要回到起点卸下再出发。给出n个苹果树顺时针的位置及苹果的个数。求摘全然部苹果走的最小路程

题目分析：显然。仅仅有在某种特殊条件下，即两側都还有苹果且能够一次装完且最后的苹果都离起点比較远。这样的情况下。我们直接绕圈可能会更优，也就是说整圈最多绕一次。因此我们能够先对两边贪心。题目的数据显示苹果的数量最多就1e5，显然我们能够把苹果“离散”出来，用x[i]记录第i个苹果到起点的位置。然后对位置从小到大排序，先选择路程小的。选择的时候用dis[i]记录单側装了i个苹果的最小路程，类似背包计数的原理。答案要乘2，由于是来回的，最后在k>=i时。枚举绕整圈的情况，szl－i表示仅仅走左边採的苹果数，szr - (k - i)表示仅仅走右边採的苹果树。画个图就能看出来了。注意右边这里可能值为负。要和0取最大，然后答案就是（disl[szl－i] + disr[szr - (k - i)]）* 2 ＋L，这里事实上绘图更加直观。最后取最小就可以，注意有几个wa点，一个是要用long long。二是之前说的出现负数和0取大，三是每次要清零

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #define ll long longusing namespace std;int const MAX = 1e5 + 5;int  L, n, k;ll x[MAX], disl[MAX], disr[MAX];vector 
          
            l, r;int main(){    int T;    scanf("%d", &T);    while(T--)    {        memset(disl, 0, sizeof(disl));        memset(disr, 0, sizeof(disr));        l.clear();        r.clear();        scanf("%d %d %d", &L, &n, &k);        int cnt = 1;        for(int i = 1; i <= n; i++)         {            ll pos, num;            scanf("%lld %lld", &pos, &num);            for(int j = 1; j <= num; j++)                x[cnt ++] = (ll) pos;   //离散操作        }        cnt --;        for(int i = 1; i <= cnt; i++)        {            if(2 * x[i] < L)                l.push_back(x[i]);            else                r.push_back(L - x[i]);  //记录位置        }           sort(l.begin(), l.end());        sort(r.begin(), r.end());        int szl = l.size(), szr = r.size();        for(int i = 0; i < szl; i++)            disl[i + 1] = (i + 1 <= k ? l[i] : disl[i + 1 - k] + l[i]);        for(int i = 0; i < szr; i++)            disr[i + 1] = (i + 1 <= k ? r[i] : disr[i + 1 - k] + r[i]);        ll ans = (disl[szl] + disr[szr]) * 2;        for(int i = 0; i <= szl && i <= k; i++)        {            int p1 = szl - i;            int p2 = max(0, szr - (k - i));            ans = min(ans, 2 * (disl[p1] + disr[p2]) + L);        }        printf("%I64d\n", ans);    }}

转载地址：http://bzljx.baihongyu.com/

你可能感兴趣的文章