开发笔记:兼职

package tree;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/**
* 如果先不考虑业务日程，求最小费用，每组折扣，可以选择多个，是个完全背包问题；
* 其中，费用种类总和K为物品数量，费用信息的每组人数为权重w[i]，每组费用为物品价值v[i]，业务日程数量M为背包容量；
*
* 求每天的工作需要的员工人数有两种方法：
* 1.差分数组
* 2.Indexed Tree， 用Indexed Tree时，query方法和update方法与平时的相反
* @author XA-GDD
*
*/
public class Freelancer_0322 {
static int T,N,M,K;
static int _max_Nval = 100000;
static int _max_Mval = 200000;
static int _max_Kval = 100;
static int [][] work = new int[_max_Mval+1][2];
static int [][] fee = new int[_max_Mval+1][2];
static long [] dp = new long[_max_Mval+1];
static int [] empCnt = new int[_max_Nval+2];
static int [] idxTree = new int[_max_Nval*4];
static int offset;
static long ANS;
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("D:\\\\workspace\\\\sw_pro\\\\test_case\\\\sample_input_0322.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
T = Integer.parseInt(st.nextToken());
for(int testCase = 1; testCase<=T;testCase++) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());

Arrays.fill(empCnt, 0);
Arrays.fill(dp, 1,M,Long.MAX_VALUE);
Arrays.fill(idxTree, 0);
for(int i=0;i Arrays.fill(fee[i], 0);
}
ANS=0L;

//业务日程
int maxDate = 0;
for(int i=0;i st = new StringTokenizer(br.readLine());

int startDate = Integer.parseInt(st.nextToken());
int endDate = Integer.parseInt(st.nextToken());
maxDate = Math.max(maxDate, endDate);


//方法1：差分数组 ======start=========
// empCnt[startDate]++;
// empCnt[endDate+1]--;
//方法1：差分数组 ======end=========

//方法2：Indexed Tree ======start=========
work[i][0] = startDate;
work[i][1] = endDate;
//方法2：Indexed Tree ======end=========
}

//方法1：差分数组 ======start=========
// for(int i=1;i<=maxDate;i++) {
// empCnt[i] += empCnt[i-1];
// }
//方法1：差分数组 ======end=========

//费用
for(int i=0;i st = new StringTokenizer(br.readLine());
fee[i][0] = Integer.parseInt(st.nextToken());
fee[i][1] = Integer.parseInt(st.nextToken());
}

//完全背包
for(int i=0;i for(int j=fee[i][0];j<=M;j++) {
dp[j] = Math.min(dp[j], dp[j-fee[i][0]]+fee[i][1]);
}
}

//方法1：差分数组 ======start=========
// for(int i=0;i<=maxDate;i++) {
// ANS += empCnt[i]>N? dp[empCnt[i]-N]:0;
// }
//方法1：差分数组 ======end=========


//方法2：Indexed Tree ======start=========
int k=0;
while((1< k++;
}
offset=1< for(int i=0;i update(offset+work[i][0],offset+work[i][1]);
}
for(int i=1;i<=maxDate;i++) {
int currEmpCnt = query(offset+i);
ANS += currEmpCnt>N? dp[currEmpCnt-N]:0;
}
//方法2：Indexed Tree ======end=========

System.out.printf("#%d %d\\n",testCase,ANS);
}

}

static void update(int start ,int end) {
while(start<=end) {
if(start%2==1) {
idxTree[start]++;
}
if(end%2==0) {
idxTree[end]++;
}
start=(start+1)>>1;
end = (end-1)>>1;
}
}

static int query(int index) {
int res=0;
while(index>0) {
res += idxTree[index];
index = index>>1;
}
return res;
}
}