如果最大值比剩余两个加起来的总和+1还大,就是NO,否则是YES

#include<bits/stdc++.h>
using namespace std;
int main(){
int T;
cin>>T;
while(T--){
vector<int> a(3);
for(int i=0;i<3;i++)
cin>>a[i];
sort(a.begin(),a.end());
if(a[2]>a[0]+a[1]+1) puts("No");
else puts("Yes");
}
}

  

先不要去考虑跳过的问题,就让他一直向前走,并且一直减,并且记录途中遇到的礼物最大值,这样有两种情况

case1:直接走完,答案就是0

case2:停在某一个位置,我们一定会选择所有可能跳过的礼物中最大的,因为必须要放弃一个,肯定要放弃其中最大的

#include<bits/stdc++.h>

using namespace std;

int main(){
int T;
scanf("%d",&T);
while(T--){
int n,sum;
scanf("%d%d",&n,&sum);
vector<int> a(n);
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
int pos=0;
int i;
for(i=0;i<n;i++){
if(sum>=a[i]) {
sum-=a[i];
}
else {
if(a[pos]<a[i]) pos=i;
break;
}
if(a[pos]<a[i]) pos=i;
}
if(i==n) printf("0\n");
else{
printf("%d\n",pos+1);
}
}
}

  

对于被拿出来的,不需要去管他究竟是按什么放回去的,但是可以肯定的是必然有一种方案是最优的,使得如果不取更深的礼物的话花费一定是1

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e5+5;

int a[maxn],b[maxn],pos[maxn];

int main(){
int T;
scanf("%d",&T);
while(T--){
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
scanf("%d",&a[i]),pos[a[i]]=n-i;
for(int i=0;i<m;i++)
scanf("%d",&b[i]);
int in=n,out=0;
long long ans=0;
for(int i=0;i<m;i++){
if(pos[b[i]]<=in) {
ans+=2*(in-pos[b[i]]+out)+1;
in=pos[b[i]]-1;
out=n-i-1-in;
}
else ans++,out--;
}
printf("%lld\n",ans);
}
}

  

遍历每一个礼物,很容易算出每一个礼物被选中的概率,然后考虑有多少个人需要这个礼物,假设为cnt,这个可以预处理出来,选中这些人的概率为cnt/n

两个相乘即可,所有的情况加起来即可

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e6+5;
const int P=998244353; int add(int a,int b){
int ans=a+b;
if(ans>=P) ans-=P;
return ans;
} int mul(int a,int b){
return 1ll*a*b%P;
} int qpow(int a,int n){
int ans=1;
for(;n;n>>=1,a=1ll*a*a%P)
if(n&1) ans=1ll*ans*a%P;
return ans;
} vector<int> a[maxn]; int inv[maxn]; int main(){
int n;
scanf("%d",&n);
vector<int> cnt(maxn,0);
for(int i=0;i<n;i++){
int x;
scanf("%d",&x);
a[i].resize(x);
for(int j=0;j<x;j++)
scanf("%d",&a[i][j]);
for(int j=0;j<x;j++)
cnt[a[i][j]]++;
}
for(int i=0;i<maxn;i++)
inv[i]=qpow(i,P-2);
int ans=0;
for(int i=0;i<n;i++){
for(int j=0;j<a[i].size();j++){
ans=add(ans,mul(mul(inv[n],inv[a[i].size()]),mul(inv[n],cnt[a[i][j]])));
}
}
printf("%d\n",ans);
}

  

最新文章

  1. rem的使用
  2. django例子,question_text为中文时候报错
  3. K-邻近算法
  4. WPF 窗口自定义拉伸
  5. iOS 黑屏
  6. 机器学习中的数学(5)-强大的矩阵奇异值分解(SVD)及其应用
  7. java结构与算法之冒泡排序
  8. log4j 实例 , 浅析
  9. linux 如何打包代码
  10. join和wait
  11. 几种移动app API调用认证方案浅析
  12. jenkins学习之自动打包构建nodejs应用
  13. discuz7.2 faq.php 注入漏洞分析
  14. 8天入门docker系列 —— 第一天 docker出现前的困惑和简单介绍
  15. 跟我一起学opencv 第五课之图像的混合
  16. QT+VS2013 * 获取网络时间
  17. oracle开发错误
  18. js常用判断和语法
  19. 安装Vue和创建一个Vue脚手架项目
  20. windows下openssl编译

热门文章

  1. 在C#中通过使用Newtonsoft.Json库来解析百度地图地理编码(GeoCoder)服务接口返回的Json格式的数据
  2. tomcat 安装在 linux
  3. 联合索引在B+树上的存储结构及数据查找方式
  4. C# 获取键盘钩子,屏蔽键盘按键
  5. mysql中EXPLAIN 的作用
  6. Linux 文件|目录 属性
  7. Chrome的插件扩展程序安装目录
  8. Apache Solr JMX服务远程代码执行漏洞复现
  9. JS淘宝小广告
  10. 清北学堂—2020.1提高储备营—Day 4 afternoon(动态规划初步(一))