Delicious Apples
Time Limit: 5000/3000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 587 Accepted Submission(s): 188
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.
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.
Next n lines,
each line contains xi,ai.
the number of testcases.
Then t testcases
follow. In each testcase:
First line contains three integers, L,n,K.
Next 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
题目大意：有一个圈。圈的长度是l，在正上方是0点，在圈上有n棵苹果树，给出每棵苹果树的位置和苹果的数量，如今一个人在0点的农场里。有一个小篮子。一次能够装k个苹果，问最少走多少距离能够把苹果收回农场。
赛中一看就是贪心的题目，然后就是各种不会啊，当时想了各种办法，又想了各种反例。，，，终于还是不会，。。
赛后补题。结论：表示一定要注意给出的范围的条件呀，尤其是比較特别的。一定实用。
对于摘苹果有几种情况：
1、正向去摘。然后按原路返回
2、反向去摘，然后按原路返回
3、还有就是直接走一圈
这三种方式，前面两个是比較easy解决的，直接去摘就好，特别的是去直接走一圈，假设两側都有非常多。那么直接走一圈一定是浪费的，那么会在什么情况下会变成节省路程的呢？
结果就是假设在圈上仅仅剩下了k个苹果，能够一次摘走，假设这k个在一側，或者在接近0点的两側，那么走半圆是优的；假设在两側并且比較靠下方。那么直接走一圈就是优的。并且走一圈仅仅可能出现一次，否则就能够用半圈来取代了。
题目中给出了全部的苹果不会超过10^5个，让a[i]表示第i个苹果的位置。disr[i]表示正向摘完第i个须要的距离，disl[i]表示反向摘完第i个须要的距离，然后通过它们找出假设没走过整圈须要的最小值，和走一个整圈须要的最小值。当中小的那个是结果。
注意：假设k大于全部的苹果数，那么len的距离一定能够摘完，要特判一下最小值。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define LL __int64
struct node{
int x , a ;
}p[100010];
int a[100010] , cnt ;
LL disl[100010] , disr[100010] ;
int cmp(node t1,node t2) {
return t1.x < t2.x ;
}
int main() {
int t , n , k ;
int i , j ;
LL len , ans ;
scanf("%d", &t) ;
while( t-- ) {
scanf("%d %d %d", &len, &n, &k) ;
for(i = 0 ; i < n ; i++) {
scanf("%d %d", &p[i].x, &p[i].a) ;
}
sort(p,p+n,cmp) ;
cnt = 1 ;
for(i = 0 ; i < n ; i++) {
for(j = 0 ; j < p[i].a ; j++)
a[cnt++] = p[i].x ;
}
memset(disl,0,sizeof(disl)) ;
memset(disr,0,sizeof(disr)) ;
for(i = 1 ; i < cnt ; i++) {
j = max(i-k,0) ;
disr[i] = disr[j] + 2*a[i] ;
}
for(i = cnt-1 ; i > 0 ; i--) {
j = min(i+k,cnt) ;
disl[i] = disl[j] + 2*(len-a[i]) ;
}
ans = 0 ;
for(i = 0 ; i < cnt ; i++) {
if( ans == 0 ) ans = disr[i] + disl[i+1] ;
else ans = min(ans,disr[i]+disl[i+1]) ;
}
for(i = 0 ; i+k+1 <= cnt ; i++)
ans = min(ans,disr[i]+disl[i+k+1]+len) ;
if( k >= cnt ) ans = min(ans,len) ;
printf("%I64d\n", ans) ;
}
return 0 ;
}