CF tracker
Edu List
https://codeforces.com/contest/1728
F. Fishermen
n个钓鱼人
第i个获得大小a[i]的鱼
他们选一个报告的顺序, 报告鱼的大小b[i], 但是可能虚报
第一个报告的 诚实报告
其它人报告的 是最小的b[i]=a[p[i]]的倍数 且 大于 前一个报告值
1
2
3
| 1 2 3 2 2 8 3
按顺序报 变成
1 2 3 4 4 8 9
|
对于所有报告顺序, 让所有报告的 sum b[i] 最小
输出sum b[i]的最小值即可
范围
n 1000
ai [1,1e6]
6s
512mb
我的思路
如果两两不同, 那么从小到大就好了, 因为b[i] >= a[i], 这是所有都取a[i] 是最小值
如果 两个相同, 那么至少一个要虚报, 那么至少 2a[i]
如果 三个相同, 那么=> a[i], 2a[i], 3a[i]
但不只是让它们不同就完了, 因为翻倍后依然可能相同
这两个6还要处理
但是一个6是变8, 一个是变9
显然 如果a 有重复n次, 那么 a,2a,…,na 一定都有的,不会中间空着, 否则把更大的来填补可以让它更小
感觉上 当倍增的时候遇到相同的, 那就让小的去增加,
但实际上
1
2
3
4
| 2 2 2 2 3 3
变成
2 4 6 8
3 6
|
如果是 2的6去变化, 那么要变成16, 不如3的6变成9
而变化, 因为上面说了不会中间空着, 那就是每次找 最大的倍数去变
这样靠差值最小来变化的贪心, 似乎是对的吗???? 但我证明不了
然后 如果这样搞, 运算量
似乎也就O(2n)?
写了下, 不出所料 样例都没过
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}
int main(){
int n=read();
map<ll,vector<pair<ll,int> > > v2tv;
rep(i,0,n){
int a=read();
v2tv[a].push_back({1,a});
}
map<ll,ll> v2mxt;
ll ans=0;
while(v2tv.size()){
auto [k,arr]=*v2tv.begin();
v2tv.erase(v2tv.begin());
auto keep=arr[0];
rep(i,1,size(arr)){
auto [kt,kv] = keep;
auto [nt,nv] = arr[i];
if(!v2mxt.count(kv)) v2mxt[kv]=1;
if(!v2mxt.count(nv)) v2mxt[nv]=1;
ll nkt=v2mxt[kv]+1;
ll nnt=v2mxt[nv]+1;
if(nkt*kv < nnt*nv){
v2mxt[kv]=nkt;
v2tv[nkt*kv].push_back({nkt,kv});
keep=arr[i];
}else{
v2mxt[nv]=nnt;
v2tv[nnt*nv].push_back({nnt,nv});
}
}
printf("%d -> %lld\n",keep.second,keep.first*keep.second);
ans+=k;
}
printf("%lld\n",ans);
return 0;
}
|
1
2
3
4
5
6
7
8
| 1 -> 1
2 -> 2
3 -> 3
2 -> 4
3 -> 6
8 -> 8
2 -> 10
34
|
问题就在6的地方是动2还是动3, 动2是先到8再到10, 这个8 能预判吗??
并不会