C. Qpwoeirut And The City Codeforces Round #809 (Div. 2)
admin
2024-03-07 14:38:41
0次

传送门

题意:有n栋楼,每栋楼的高度为a_i,对美丽的楼的定义如下:

对于2<=i<=n-1,如果a_i>a_i-_1并且,a_i>a_i+_1那么就说明这栋楼是美丽的。(所以第一栋楼和最后一栋一定不是美丽的)

lk现在可以将所有的楼的高度增加任意值,他想知道他能获得的最多的美丽的楼的前提下花费最小为多少。

思路:

首先对于2-n 的下标进行处理,如果将该栋楼变成美丽的就视为1,否则视为0.

预处理v数组算出将v_i栋楼变成美丽楼的代价,

n为奇数的话,因为只有一种可能的情况,就是1010101....,直接算出所有要变成的美丽楼的代价。

如果n为偶数:假设n为8的情况,去掉第一个和最后一个,我们可以直接求出所有的规律:

//101010
//101001
//100101
//010101

那么我们可以发现,对于后面是10 的,那么前面一定不能变成01,那么对于有01的情况,一定是从末尾开始变,一直变到第一个。

那么可以直接先计算出全部为10的结果,然后每次将后面的10转换成01然后取最小值,最后的结果就是我们的答案。

/**
*  ┏┓   ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃       ┃
* ┃   ━   ┃ ++ + + +
*  ████━████+
*  ◥██◤ ◥██◤ +
* ┃   ┻   ┃
* ┃       ┃ + +
* ┗━┓   ┏━┛
*   ┃   ┃ + + + +Code is far away from  
*   ┃   ┃ + bug with the animal protecting
*   ┃    ┗━━━┓ 神兽保佑,代码无bug 
*   ┃  	    ┣┓
*    ┃        ┏┛
*     ┗┓┓┏━┳┓┏┛ + + + +
*    ┃┫┫ ┃┫┫
*    ┗┻┛ ┗┻┛+ + + +
*/#include
#include 
#include 
#include 
#include 
#include 
#include
#include
#include
#define sc_int(x) scanf("%d", &x)
#define sc_ll(x) scanf("%lld", &x)
#define pr_ll(x) printf("%lld", x)
#define pr_ll_n(x) printf("%lld\n", x)
#define pr_int_n(x) printf("%d\n", x)
#define ll long long 
using namespace std;const int N=100100+100;
const ll INF=1e18;
int n ,m,h;
ll s[N];
ll v[N];int main()
{int t;sc_int(t);while(t--){sc_int(n);	memset(v,0,sizeof v);for(int i =1;i<=n;i++)sc_ll(s[i]);if(n%2!=0){ll res=0;for(int i=2;i<=n;i+=2)if(s[i]<=max(s[i-1],s[i+1]))res+=max(s[i-1],s[i+1])-s[i]+1;pr_ll_n(res);}else{ll res=INF,sum=0;for(int i =2;i2;i-=2) // 1     2 3 4 5     6{sum-=v[i-1];sum+=v[i];res=min(res,sum);}pr_ll_n(res);}	}return 0;
}

相关内容

热门资讯

蜻蜓订购APP贵金属订购非法期...   蜻蜓订购APP以"投资平台"名义对外宣传,主打贵金属期货(订购)交易。该平台一方面强调自身"正规...
悟空订购APP非法期货交易欺骗...   近期,有投资者反映,“悟空订购APP”等平台以白银、贵金属订购为名,宣传所谓“高收益”“低门槛”...
小赢淘金APP期货投资骗局,平...   “小赢淘金”之流,最擅长的就是用“注册送现金”、“充值返券”的糖衣炮弹来引流。别天真地以为那是福...
八方淘金APP非法期货交易欺骗...   警惕!八方生财、每日淘金、小赢淘金、悟空订购、蜻蜓订购、斗金订购等APP均涉嫌非法期货交易!  ...
智易购APP贵金属订购交易骗局...   很多人看到“3元起投”“充值送福利”“操作简单”“随时提现”这类宣传,很容易把智易购APP当成普...
喜玛银庄APP商品订购投资骗局...   喜玛银庄APP白银、铂金“现货订购”骗局警示:无资质平台涉嫌非法期货交易,投资者爆仓后如何维权?...
吉鑫乐享APP炒贵金属订购交易...   近期,多名投资者反映在“吉鑫乐享APP”进行贵金属投资时遭遇严重亏损,甚至血本无归。看似正规的“...
易掘金APP虚假期货投资骗局,...   “易掘金”的APP它打着“高收益、灵活投资”的旗号,宣称通过“商品订购”就能轻松赚钱,吸引了不少...
在大吉订购APP订购交易亏损被...   近期,不少投资者反映在“大吉订购App”上投资白银、铂金等商品遭遇严重亏损。该平台宣称提供现货订...
铂银壹号APP商品订购交易亏损...   许多中小投资者误以为网上的“商品现货订购”是合规合法的理财渠道,殊不知这背后隐藏着巨大的合规风险...
兴鑫淘金APP贵金属订购交易亏...   白银、贵金属或其他商品类投资,除国家批准的正规期货交易场所及持牌期货公司外,市面上大量第三方交易...
铂银掘金APP无资质的违规平台...   铂银掘金等平台的投资者,往往是被“注册送现金”“充值返现券”“首单免亏”等广告话术吸引,进而下载...
八方淘金APP订购交易不合规,...   “八方淘金APP”“铂银掘金APP”“铂银壹号APP”等软件被指以“现货订购”为名,实际采用高杠...
在指尖订购APP订购商品亏损被...   指尖订购APP这类平台,表面是“订购交易”,实则是披着电商外衣的非法期货陷阱。绝大多数投资者被蒙...
在犀贝易购APP做商品订购交易...   市面上打着“现货投资”“贵金属交易”旗号的APP并不少,但真正合规、受监管的平台并不多。犀贝易购...
易达淘金APP虚假商品订购交易...   易达淘金APP存在严重的虚假宣传与违规交易行为。该平台打着“商品订购”的旗号,实则通过不合规的交...
大浪淘金APP白银订购亏损被骗...   大浪淘金APP最隐蔽的套路,在于其完全封闭的内盘交易系统。表面上,它宣称与国际贵金属市场接轨;实...
一品好购APP上订购白银出现亏...   一品好购APP原名“一品订购”,运营方为上海宝智未来信息技术有限公司。近期不少投资者反映在该平台...
九州订购APP贵金属订购投资骗...   九州订购APP正通过抖.音、快手、今日头条等平台大量投放投资广告,用“5元起投”“充值返现”“0...
坚锅淘金APP交易软件并不正规...   当前,市面上大量所谓的“现货商城订购”交易软件,早已偏离了正常的实物商品买卖,演变为高杠杆、高手...