[Codeforces] 731F. Video Cards

題目連結:http://codeforces.com/problemset/problem/731/F
惹...原來可以暴力做。直接枚舉每個人$i$當作leader時的情況,而計算時就是要算$[ik, i(k+1))$的數字數有幾個,因為在這區間的數字$a$再扣完之後一定都變成$ik$。此外枚舉倍數是$nlogn$的(某種調和級數的想法),所以就照著做囉(?
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int N = 200000 + 5;

lld sum[N];
bool isok[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n;i++){
		int x; cin>>x;
		sum[x]++;
		isok[x]=1;
	}
	for(int i=1;i<N;i++) sum[i]+=sum[i-1];
	lld ans = 0;
	for(int i=1;i<N;i++){
		if(!isok[i]) continue;
		lld cur = 0;
		for(int j=i;j<N;j+=i) cur += j*(sum[min(j+i,N)-1]-sum[j-1]);
		ans = max(ans, cur);
	}
	cout<<ans<<'\n';
	return 0;
}

留言

  1. 提示一下!這邊的 isok[i] 其實可以用 sum[i] - sum[i-1] > 0 來取代喔!

    回覆刪除
    回覆
    1. 恩恩,的確可以,不過當時寫的時候沒想太多,反正會過就好,也沒差太多時間或記憶體,就選個自己比較直覺的方式寫了

      刪除
  2. 而且 sum[min(j+i,N)-1] 應該改成 sum[min(j+i-1,N)] 比較合理?

    回覆刪除
    回覆
    1. 沒有仔細想,但純論記憶體的角度來看這樣是錯的吧,畢竟sum[N]是個不該被使用的記憶體位置

      刪除
    2. 喔喔喔,我沒注意到最後一個 index 應該是 N-1,那就沒事ㄌ。
      沒有想到作者竟然會回覆,還是很感謝作者的 code,小弟終身受用!而且這個網站的顏色排版還蠻美的,是值得小弟模仿的對象ㄋ!

      刪除

張貼留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology