2020-08-09
http://icpc.upc.edu.cn/problem.php?id=14866
题目
14866: 高兴天数
题目描述
小X性格很独特，如果她今天高兴度比上次一样或更高，她就会很善良，相反，如果她今天高兴度比上次低，她就会很凶！现在已经知道小X在N天里每天的高兴度M。根据这N天中她每天高兴度M，合理安排与她相处时间，使大家与小X友好相处尽量多天数。现在要求计算出最多能和小X友好相处多少天。
输入
共2行，第一行为一个N，第二行为N个数，为小X每天的高兴程度M。
输出
共1个数，最多能和小X友好相处多少天。
样例输入
5
2 3 5 6 4
样例输出
4
提示
对于30%的数据，N<=8000
对于100%的数据，N，M<31000
解析
二分法求最大上升子序列
这里解释一下：题目所说的“比上次”是指我们和她相处的上一次，而不是指前一天。例如，第三天和她相处后隔了两天后即第六天又与她相处，应该拿第六天心情和第三天心情比较。
#include
#include
using namespace std;
typedef long long ll;
ll a[300500]={0};
ll c[300500]={0};
int main()
{
ll n,cnt=0;
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
scanf("%lld",a+i);
for(ll i=1;i<=n;i++)
{
if(a[i]>=c[cnt])
{
c[++cnt]=a[i];
}
else
{
ll l=1,r=cnt+1;
while(lc[mid])
{
l=mid+1;
}
else if(a[i] http://icpc.upc.edu.cn/problem.php?id=15036
题目
15036: 选择
题目描述
哈哈哈，快忘掉你的烦心事，找张位子坐下来。
beny和fife两人作为彼此炉边好友，决定来一场惊心动魄的友谊（py）赛。
fife有n个随从，第i个随从有一个能力值，为A[i]。
beny也有对应的n个随从，第i个随从同样也有一个能力值，为B[i]。
然后，一群随从的战斗力为这群随从能力值的总和。
现在，beny和fife每个人都派出自己第L个到第R个（共R-L+1个随从），来一决高下。
但是由于他们在一绝高下的同时要py任务，他们要你选择一对(L,R)，使双方战斗力差距最小。
他们要你输出最小的战斗力差距（战斗力较大的减战斗力较小的）。
输入
第一行一个正整数n。
第二行n个整数，表示数组A。
第三行n个整数，表示数组B。
输出
一行一个正整数， 表示最小的战斗力差距。
样例输入
【样例1】
3
4 2 3
3 4 2
【样例2】
5
38 19 5 17 3
15 22 0 6 17
样例输出
【样例1】
0
【样例2】
1
提示
样例1解释：L = 1， R = 3
样例2解释：L = 2， R = 5
set的应用
#include
using namespace std;
typedef long long ll;
ll a[300500]={0};
ll b[300500]={0};
ll c[300500]={0};
set::iterator it1,it2;
ll x,y,n,ans=99999999999;
setw;
int main()
{
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
for(ll i=1;i<=n;i++)
{
scanf("%lld",&b[i]);
c[i]=c[i-1]+b[i]-a[i];
}
w.insert(0);
w.insert(99999999999);
for(ll i=1;i<=n;i++)
{
it1=w.upper_bound(c[i]);
it2=it1;
it2--;
x=*it1;
y=*it2;
ans=min(ans,abs(c[i]-x));
ans=min(ans,abs(c[i]-y));
w.insert(c[i]);
}
printf("%lldn",ans);
}
