You helped Dima to have a great weekend, but it’s time to work. Naturally, Dima, as all other men who have girlfriends, does everything wrong.
Inna and Dima are now in one room. Inna tells Dima off for everything he does in her presence. After Inna tells him off for something, she goes to another room, walks there in circles muttering about how useless her sweetheart is. During that time Dima has time to peacefully complete k - 1 tasks. Then Inna returns and tells Dima off for the next task he does in her presence and goes to another room again. It continues until Dima is through with his tasks.
Overall, Dima has n tasks to do, each task has a unique number from 1 to n. Dima loves order, so he does tasks consecutively, starting from some task. For example, if Dima has 6 tasks to do in total, then, if he starts from the 5-th task, the order is like that: first Dima does the 5-th task, then the 6-th one, then the 1-st one, then the 2-nd one, then the 3-rd one, then the 4-th one.
Inna tells Dima off (only lovingly and appropriately!) so often and systematically that he’s very well learned the power with which she tells him off for each task. Help Dima choose the first task so that in total he gets told off with as little power as possible.
Input The first line of the input contains two integers n, k (1 ≤ k ≤ n ≤ 105). The second line contains n integers a1, a2, …, an (1 ≤ ai ≤ 103), where ai is the power Inna tells Dima off with if she is present in the room while he is doing the i-th task.
It is guaranteed that n is divisible by k.
Output In a single line print the number of the task Dima should start with to get told off with as little power as possible. If there are multiple solutions, print the one with the minimum number of the first task to do.
Example Input 6 2 3 2 1 6 5 4 Output 1 Input 10 5 1 3 5 7 9 9 4 1 8 5 Output 3
题意：给出n样属性，求满足 （糖果的口味）sum1/sum2（糖果的重量） ==k 的情况下的sum1的最大值，除法是没有办法进行加减的，所以要转化一下，c[i]=a[i]-k*b[i] 作为平衡度, 这个平衡度可以进行加减，如果平衡度为负说明，糖果的重量较大，平衡度为负说明糖果的重量较小，如果平衡度相等 这种情况下 平衡度加起来依然是满足 平衡度为0的条件，由于只要求取得刚好满足k也就是刚好满足表达式为0，也就是背包填满的情况，所以除了dp[0]=dd[0]为0，其他为负无穷，说明只能由0来演变状态。背包的最大容量为平衡度，上界推出来为10000，c[i]要分正负情况来写，最后求在平衡度为i的时候，糖果的口味和糖果的重量都满足平衡度i 加起来i-i=0，也就是满足表达式为0。得到的结果取最大。
#include <bits/stdc++.h> using namespace std; int a[101010]; int b[101010]; int c[101010]; int dp[101010]; int dd[101010]; const int inf = -0x3f3f3f3f; int main() { int n, k; cin >> n >> k; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) cin >> b[i]; for(int i = 1; i <= n; i++) c[i] = a[i] - k * b[i]; memset(dp, inf, sizeof(dp)); memset(dd, inf, sizeof(dd)); dp[0] = 0; dd[0] = 0; for(int i = 1; i <= n; i++) { if(c[i] >= 0) for(int j = 10000; j >= c[i]; j--) { dp[j] = max(dp[j],dp[j-c[i]]+a[i]); } } for(int i = 1; i <= n; i++) { if(c[i]<0) { c[i] = -c[i]; for(int j = 10000;j >= c[i]; j--) dd[j] = max(dd[j],dd[j-c[i]]+a[i]); } } int ans = 0; for(int i = 10000; i >= 0; i--) { ans=max(ans,dp[i]+dd[i]); } if(!ans) printf("-1\n"); else printf("%d\n",ans ); }