題目鏈接：http://codeforces.com/problemset/problem/334/C

題目：

題目大意：

給定數(shù)字n，要求構(gòu)建一個(gè)數(shù)列使得數(shù)列的每一個(gè)元素的值都是3的次方，數(shù)列之和S大于n，且刪掉數(shù)列中的任意一個(gè)元素?cái)?shù)列之和都會(huì)小于n，最大化這個(gè)數(shù)列的長(zhǎng)度

題解：

我們考慮從小到大枚舉k，取最小的k，使得，答案就是$n/3^k+1$

為什么呢？

我們考慮一個(gè)合法的數(shù)列，其中最小的元素是A，那么S一定是A的倍數(shù)。假設(shè)n是A的倍數(shù)，又S>n，那么S-A>=n，這樣的話去掉A這個(gè)數(shù)列依舊大于等于n，數(shù)列就不合法了。

所以我們有n一定不是A的倍數(shù)。

于是我們從小到大枚舉A的大小，直到找到最小的A滿足n不是A的倍數(shù)，那么就直接用面值為A的硬幣就可以了。

也許有為什么不用更大的滿足n不是A的倍數(shù)的A的疑惑，其實(shí)更大的話也都可以表示成最小的A的倍數(shù)，那顯然是沒有用A優(yōu)的

#include <cstdio> #include <iostream> #include <cstring> #include <algorithm> using namespace std;long long n; int main() {cin>>n;while(n%3==0){n/=3;}cout<<n/3+1<<endl;return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/xxzh/p/9614203.html

總結(jié)

以上是生活随笔為你收集整理的[Codeforces Round #194 (Div. 2)] Secret 解题报告 （数学）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。