codeforces 206 div.1

本文从WordPress迁移而来, 查看全部WordPress迁移文章

A.题意:每个物品有一个价值w[i]，如果用机器人左臂去拿最左边的物品，每个物品还要wl,如果用机器人右臂去拿则wr,如果用左臂连续拿了几个物品，那么从第2个物品开始每个物品要附加一个权值ql；如果连续 用右臂拿物品从第2个物品开始每个物品附加一个权qr；取完所有物品花费最小

一开始想到DP，后来想清楚了，主要是用左臂拿还是右臂拿的问题，无论怎么拿，假设最后拿走的物品是第m个物品，那么可知 ，1到m-1号物品一定都是左臂拿的，因为拿东西只能从端点拿，m号是最后拿走的，那么之前它一直存在，1到m-1号的物品是不可能通过右臂拿到的，同理，m+1到n号的物品一定是通过右臂拿到的，至于m号物品，最后只剩下它，可以左臂或者右臂拿，枚举一次即可。另外1到m-1号是左臂拿的，m+1号到n号是右臂拿的，具体怎么拿，那肯定是错开开，左边拿一个，右边拿一个，这样才能最大限度地避免因为连续拿物品而产生的附加花费，但即便是错开拿，有些情况下还是要连续拿物品的（因为左边和右边的物品数不一定相同） 做法就是枚举最后拿的物品m，m把线段分成左右两部分，左边一定是左臂拿，右边一定右臂拿，另外枚举m是哪个臂拿，再计算连续拿东西产生的花费

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp mkae_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define N 100010
#define INF 2000000000

int n,w[N],wl,wr,ql,qr;
int lw[N],rw[N],sumlw[N],sumrw[N];
int main(){
	while(scanf("%d%d%d%d%d",&n,&wl,&wr,&ql,&qr)!=EOF){
		cl(sumlw,0); cl(sumrw,0);
		for(int i = 1; i <= n; i++){
			scanf("%d",&w[i]);
			lw[i] = w[i] * wl;
			rw[i] = w[i] * wr;
		}
		sumlw[1] = lw[1];
		for(int i = 2; i <= n; i++)
			sumlw[i] = sumlw[i-1] + lw[i];
		sumrw[1] = rw[n];
		for(int i = 2; i <= n; i++)
			sumrw[i] = sumrw[i-1] + rw[n-i+1];

		int ANS = INF;
		for(int last = 1; last <= n; last++){
			int lenl = last - 1;
			int lenr = n - last;
			int res[2];
			if(lenl == lenr){
				res[0] = sumlw[last] + sumrw[lenr];
				res[1] = sumlw[lenl] + sumrw[lenr+1];
			}
			else if(lenl > lenr){
				res[0] = sumlw[last] + sumrw[lenr] + ql * (last-lenr-1);
				res[1] = sumlw[lenl] + sumrw[lenr+1] + ql * (last-lenr-2); 
			}
			else{
				res[0] = sumlw[last] + sumrw[lenr] + qr * (lenr-lenl-1);
				res[1] = sumlw[lenl] + sumrw[lenr+1] + qr * (lenr-lenl);
			}
			ANS = min(ANS , min(res[0],res[1]));
		}
		printf("%d\n",ANS);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
INF = 2000000000
n , wl , wr , ql , qr = map(int , raw_input().split())
w = map(int , raw_input().split())
lw = range(n+10)
rw = range(n+10)
sumlw = range(n+10)
sumrw = range(n+10)
for i in range(1,n+1) :
    lw[i] = w[i-1] * wl
    rw[i] = w[i-1] * wr
sumlw[1] = lw[1]
for i in range(2,n+1) :
    sumlw[i] = sumlw[i-1] + lw[i]
sumrw[1] = rw[n]
for i in range(2,n+1) :
    sumrw[i] = sumrw[i-1] + rw[n-i+1]
ANS = INF
for last in range(1,n+1) :
    lenl = last - 1
    lenr = n - last
    res = range(2)
    if lenl == lenr :
        res[0] = sumlw[last] + sumrw[lenr]
        res[1] = sumlw[lenl] + sumrw[lenr+1]
    elif lenl > lenr :
        res[0] = sumlw[last] + sumrw[lenr] + ql * (last - lenr - 1)
        res[1] = sumlw[lenl] + sumrw[lenr+1] + ql * (last - lenr - 2)
    else :
        res[0] = sumlw[last] + sumrw[lenr] + qr * (lenr - lenl - 1)
        res[1] = sumlw[lenl] + sumrw[lenr+1] + qr * (lenr-lenl)
    if res[0] < ANS :
        ANS = res[0]
    if res[1] < ANS :
        ANS = res[1]
print ANS

C.题意:给出一个序列，给一个值k，序列的每个元素都可以减少k以内的数字，通过适当地调整，使得整个序列的gcd最大，输出最大点的gcd
每个数字能减少k以内的数字，转而想表达的意思是，假设有一个数字G，序列中每个元素都满足 ai % G <= k,那么这个G就是一个可行的gcd，因为每个ai都可以通过减少数值使得自己可以被G整除

找出序列中的最小值mina

若 mina <= k+1 ， 那么D答案就是mina，因为G = mina <= k+1 , ai % G < G <= k+1，即 ai % G <= k

若 mina > k+1 , 一个显然的事实是，G <= mina，那么就暴力枚举答案，从 mina—>k+2 枚举答案，不过不能暴力检验（ai%G<=k）,要利用性质

假设G是 一个可行的gcd，那么对于 所有ai都满足 ai % G <= k,换言之，ai一定落在数轴的 [G,G+k] , [2G,2G+k] , [3G,3G+k] …… [mG,mG+k]里面，那么我们只要统计一下这些区间里面一共有多少个ai，如果数目是n个，表示全部命中，G是可行解

上面一个小细节是m最多是多少，m = maxa / G

所以我们先统计区间[G,G+k],利用二分，看看序列中多少数字在里面

接着统计区间[2G,2G+k],二分

……..

[mG,mG+k],二分

代码中人肉写了两个二分查找，不过学会了两个STL，lower_bound,upper_bound,能达到两个二分查找的效果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
#define LL long long
#define pii pair<int,int>
#define pb push_back
#define mp mkae_pair
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define N 300010
#define INF 10000000

int a[N],n,k;

inline bool solve(int G){
	for(int i = 0; i < n; i++)
		if(!(a[i] % G <= k)) 
			return false;
	return true;
}

int binary1(int key){
	int low = 0 , high = n-1 , ans = -1;
	while(low <= high){
		int mid = (low+high) >> 1;
		if(a[mid] < key) low = mid + 1;
		else{
			ans = mid; high = mid - 1;
		}
	}
	return ans;
}
int binary2(int key){
	int low = 0 , high = n-1 , ans = -1;
	while(low <= high){
		int mid = (low+high) >> 1;
		if(a[mid] > key) high = mid - 1;
		else{
			ans = mid; low = mid + 1;
		}
	}
	return ans;
}

int main(){
	while(scanf("%d%d",&n,&k)!=EOF){
		int mina = INF;
		for(int i = 0; i < n; i++){
			scanf("%d",&a[i]);
			mina = min(mina,a[i]);
		}
		if(mina <= k+1){
			printf("%d\n",mina);
			continue;
		}
		sort(a,a+n);
		int res = k+1;
		for(int G = mina; G > k+1; G--){
			int cnt = 0;
			for(int m = 1; m <= a[n-1]/G; m++){
				int indexl = binary1(m*G);     // >= m*G 且下标最小
				int indexr = binary2(m*G+k);   // <= m*G+k 且下标最大
				cnt += (indexr - indexl + 1);
			}
			if(cnt == n){
				res = G; break;
			}
		}
		printf("%d\n",res);
	}
	return 0;
}