两道UVA题:UVA 12259 Fair Division , UVA 12268 Wormly

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

A. UVA 12259 Fair Division

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
81
82
/*
题意:有一个物品总价tot,n个人,每个人都有钱ai,n个人一起出钱去买这个物品,要求在能买到的情况下,满足每个人出的钱尽量平均,差距最小,另外拥有钱多的人尽量承担更多的花费,如果有人钱相同,编号小的人先承担。例如有5个人,要3元,那么应该平均,3个人每个人出1块,选这3个人的方法是,先选钱最多的3个,如果钱相同选编号最小的
整个题目的做法是,先看所有人的钱加起来能不能买下这个物品,不能的话直接IMPOSSIBLE,能的话,就一定能买下,而且付钱的方法是唯一的
迭代:
1.当前有m个人,剩下要付的钱tot,求出每个人需要付的钱ave
2.如果一个人当前的钱小于等于ave,那么他肯定要出掉他剩下的所有的钱,如果剩下的钱比ave多,那么就先出ave
3.看看这轮大家一共出了多少钱,用tot减去,就是下一轮需要付的钱
4.对于在这轮中,钱已经出完的人,以后都没他什么事了,所以人数减少
最后:
肯定需要付的钱是少于人数m的,所以只需要选出tot个人,没人付1块就行了,选人的方法就是前面说的。
整个过程实现的话,先对所有人排序(排序规则:钱多在前面,钱相同编号在前面),做完后再按编号排回来输出答案
*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 110

struct people{
int id,lim,val;
people(){}
people(int aa,int bb):id(aa),lim(bb){ val = 0; }
}a[N];
int tot,n;

bool CMP(people x , people y){
if(x.lim == y.lim)
return x.id < y.id;
else return x.lim > y.lim;
}

bool CMP_ID(people x , people y){
return x.id < y.id;
}

int main(){
int T;
scanf("%d",&T);
while(T--){
int sum = 0;
scanf("%d%d",&tot,&n);
for(int i = 0; i < n; i++){
int x;
scanf("%d",&x);
sum += x;
a[i] = people(i,x);
}
if(sum < tot){ puts("IMPOSSIBLE"); continue; }
sort(a,a+n,CMP);
int m = n;
while(tot){
int ave = tot / m,mm = m;
if(ave == 0){
for(int i = 0 ; i < tot; i++)
a[i].val++;
tot = 0;
}
else{
sum = 0;
for(int i = 0 ; i < mm; i++){
if(a[i].lim - a[i].val <= ave){
sum += a[i].lim-a[i].val;
a[i].val = a[i].lim;
m--;
}
else{
a[i].val += ave;
sum += ave;
}
}
tot -= sum;
}
}
sort(a,a+n,CMP_ID);
for(int i = 0; i < n-1; i++)
printf("%d ",a[i].val);
printf("%d\n",a[n-1].val);
}
return 0;
}

J. UVA 12268 Wormly

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
/*
题意:有一条虫,身体由b个小球组成(一排),下面有L个脚,L<=b,每个脚必须在一个小球下面,一个小球下面最多只能有1个脚
有一个长度为n的桥,用一个01串表示桥,0表示桥上没了一块木板,1表示有。桥保证最左端和最右端L个木板是1
虫有两种移动方法
1.选择一只脚,可以向前移动任意格,要保证,移动后,不能越过其他脚,且必须在身体下面,且所站的地方有木板。每移动一个脚无论移动多少格花费都是1
2.整个身体向前移动1格,所有脚不能动,要保证移动后所有脚还在身体下。这样的移动每次花费是1
虫最开始,身体最靠左,所以脚站在最左端L个木板上,目标是将虫的身体移动到最靠右,所有脚在最右端的L个木板上,问最小花费,移不到就IMPOSSIBLE

移动的策略是贪心,每轮的移动为:
1.将所有脚尽量向前移动到不能再移动的位置
2.身体尽量移动到不能再移动的位置

如果在移动到目标之前,脚动不了,则是IMPOSSIBLE,(如果脚能动,身体是一定能动的,如果身体已经最靠右了,那还是能动,只不过动了0)

=一开始用这个策略去模拟,移动所有脚,TLE了,然后想想,每次的移动其实都是唯一,所以每次移动所有脚后,最后一个脚应该在哪个位置是确定的,是可以一步算出来的,而身体向前尽量移动,其实就是移动到最后的脚的位置,所以我们每次只需要计算出最后一个脚的位置就行了
怎么计算最后一个脚在本轮移动后的位置?
当前身体头在head,从桥的head位置向左边数,第L个为1的位置就是最后一个脚要站的位置,如果最后一个脚在本轮无法移动,那说明其实所有脚都无法移动,说明已经IMPOSSIBLE了
所以用类似dp的方法预处理出一个数组,dp[i]表示的是,桥上i这个位置,向左边数,第L个1的位置是多少
*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
using namespace std;
#define MAX 1000010
#define LL long long

int L,B,n;
char s[MAX];
int one[MAX],p[MAX],leg[MAX];

LL solve(){
int op = 0,m = 0;
for(int i = 0; i < n; i++)
if(s[i] == '1')
one[m++] = i;
p[L-1] = 0;
for(int i = L; i < n; i++)
p[i] = s[i] == '1' ? one[++op] : p[i-1];

LL ans = 0LL;
int lastLeg = 0 , head = B-1 , tail = 0 , res = 1;
int cnt = 0;
while(true){
int pos = p[head];
if(pos == lastLeg) res = 0;
if(!res) break;

lastLeg = pos;
ans += L;
if(lastLeg+B-1 >= n){ ans += n-B-tail; tail = n-B; }
else{ ans += lastLeg-tail; tail = lastLeg; }
head = tail+B-1;
}
if(head == n-1) return ans;
else return -1LL;
}

int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d%d%s",&L,&B,&n,s);
LL ans = solve();
if(ans == -1LL) puts("IMPOSSIBLE");
else cout << ans << endl;
}
return 0;
}