Delicious Apples

Time Limit: 5000/3000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 395 Accepted Submission(s): 122

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

Recommend

wange2014 | We have carefully selected several similar problems for you:

题意：在一个圆上有n个苹果树。告诉苹果树的位置和每棵树上的苹果个数，另一个容量为K的篮子，用篮子去摘苹果，起点在位置0，重复去摘直到把全部的苹果都摘回到0，问走的最短距离为多少。

思路：首先将圆一分为二，在圆形两側能拿满的话肯定就是仅仅走半边再回去，这样比走整圈划算。另外还要想到最后两边都不足K个了。这个时候最多须要走一个整圈，我们不知道这个整圈拿了哪几个苹果，那么就枚举K个。

比赛时仅仅是想到了贪心，最后那一部分没有枚举，另外这里的苹果进行了离散化，由于苹果总数仅仅有1e5，大大简化了代码。自己当时写的太冗余=-=

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #include 
               
                #pragma comment (linker,"/STACK:102400000,102400000")#define pi acos(-1.0)#define eps 1e-6#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define FRE(i,a,b) for(i = a; i <= b; i++)#define FREE(i,a,b) for(i = a; i >= b; i--)#define FRL(i,a,b) for(i = a; i < b; i++)#define FRLL(i,a,b) for(i = a; i > b; i--)#define mem(t, v) memset ((t) , v, sizeof(t))#define sf(n) scanf("%d", &n)#define sff(a,b) scanf("%d %d", &a, &b)#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)#define pf printf#define DBG pf("Hi\n")typedef long long ll;using namespace std;#define INF 0x3f3f3f3f#define mod 1000000009const int maxn = 1e5+10;const int MAXN = 2005;const int N = 1005;ll Len,n,k,cnt;ll pos[maxn],dp_l[maxn],dp_r[maxn]; //dp[i]表示拿完前i个苹果要走的的距离和vector
                
                 posl,posr;int main(){#ifndef ONLINE_JUDGE freopen("C:/Users/lyf/Desktop/IN.txt","r",stdin);#endif ll i,j,t; scanf("%lld",&t); ll x,num; while (t--) { cnt=1; scanf("%lld%lld%lld",&Len,&n,&k); posl.clear(); posr.clear(); for (i=0;i

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

你可能感兴趣的文章