CF Gym 100637F The Pool for Lucky Ones
2024-08-22 23:12:08
题意:给你一串非负整数,可以将一个非零数减1,加到相邻的数字上,要使其中所有最大数字的和最小。
题解:模拟可以过。也可以分析,可以要减少最大数字和,如果最大数字出现大于等于3次,可以把最大数字加一,或者把某个最大数字减一,最大数字出现减少一次。但是要注意一些特殊情况,下面详述。
先扫一遍,如果最大数字为0,那么输出0,如果最大数字为1,那么如果可以合并成2的话,那么就输出2,否则输出数字和sum。否则,看最大数字出现次数,如果为一次,那么检查,周围是否有比它小3的数字,(如果只是比它小2的话,那么操作完以后至少会出现两个次大的数字),如果有还有检查一下操作前是否有次大的数字,然后根据检查情况输出Max或Max-1;如果出现两次,检查两个最大数字周围有没有比它小2的数字,如果有输出Max,没有的话输出Max+1,(Max>=2且不满足前者,周围一定有数字非零);对于次数大于等于3次的,检查最大数字周围有没有非零数字,如果有输出Max+1,否则sum-Max。
#include<cstdio>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<algorithm> using namespace std; //#define local
typedef long long ll;
const int maxn = 1e5+;
int p[maxn];
int main()
{
#ifdef local
freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
#endif // local
int n;
scanf("%d",&n);
ll Max = ;
int pos = -;
for(int i = ; i < n ;i++){
scanf("%d",p+i);
if(p[i]>Max){
Max = p[i];pos = i;
}
}
if(Max == ){ printf(""); return ;}
if(Max == ){
int sum = p[];
bool canMerge = false;
for(int i = ; i < n; i++){
sum += p[i];
if(p[i]&&p[i-]) { canMerge = true; break; }
}
if(canMerge) printf("");
else printf("%d",sum);
return ;
}
long long sum = ;
bool canMerge = false;
bool lessone = false; for(int i = pos; i < n; i++){
if(p[i] == Max) sum += Max;
}
if(sum == Max){
if(pos>) { if(p[pos-]<=p[pos]-)lessone = true; }
if(pos<n-) { if(p[pos+]<=p[pos]-)lessone = true; }
if(lessone) {
for(int i = ; i < n; i++){
if(p[i] == Max-) {
printf("%d",Max);
return ;
}
}
printf("%d",Max-);
}
else printf("%d",Max);
return ;
}
if(sum == Max*){ //keng
for(int i = pos; i < n; i++){
if(p[i] == Max){
if((i>&& p[i-]<= Max- )|| (i<n-&& p[i+] <= Max- ) ){
printf("%d",Max); return ;
}
}
}
printf("%d",Max+);
} for(int i = pos; i < n; i++){
if(p[i] == Max){
if((i>&& p[i-])|| (i<n-&& p[i+] ) )
{ printf("%d",Max+); return ; }
}
} printf("%I64d",sum-Max);
return ;
}
最新文章
- ABBA BABA statistics
- ps技巧
- Linux开放1521端口允许网络连接Oracle Listene
- js 中escape,encodeURI,encodeURIComponent的区别
- POJ 3468(树状数组的威力)
- 159. Longest Substring with At Most Two Distinct Characters
- 消息处理之performSelector
- Ajenti 1.0 发布,服务器管理系统 - 开源中国社区
- @font-face(css3属性)实如今网页中嵌入随意字体
- 【每天一道算法题】Numeric Keypad
- 简单的面向对象(OO)练习
- 如何以编程方式签署应用程序包(C ++)
- [Swift]LeetCode100. 相同的树 | Same Tree
- LinkedHashMap和HashTable
- 【比赛打分展示双屏管理系统-专业版】Other.ini 配置文件解读以及排行榜界面及专家评语提交展示等具体配置
- MapReduce全局变量之捉虫记
- window.location对象详解
- python3去除字符串中括号及括号里面的内容
- Git4:Git标签
- mysql数据库新插入数据,需要立即获取最新插入的id