Codeforces Round #723 (Div. 2)
Codeforces Round #723 (Div. 2)
A. Mean Inequality
链接https://codeforces.com/contest/1526/problem/A
题目大意:对于给定的一个原序列,通过重新排列,要构造出一种新的序列,使得新序列的每一项满足ai≠(ai-1+ai+1)/2,如果是第一个或者最后一个,就按照环形考虑
思路:先思考什么样的序列会不满足要求,显然可以得到,当一个序列含有等差数列时,会出现ai=(ai-1+ai+1)/2,既然如此,假设原序列就是一个等差数列,那么我们只要两两交换一下,就一定能破坏掉等差的性质,所以具体思路就是:
先对原序列排序,排完序后两两交换,不过,一开始分析的时候没考虑头和尾,对于头和尾再交换一下即可。
问题是是否存在原本不满足,但在交换后满足的情况呢？简单验证下:假设有a1,a2,a3,a4,a5考虑a3的情况,不考虑a1交换后变成,a1,a3,a2,a5,a4可以发现与a3进行比较的是比a3更小的两个数,更小的两个数的平均数是不可能比它大
的
#include <iostream>#include <algorithm>using namespace std;int t;int n;const int N=100;int a[N];int main(int argc, char *argv[]) { cin>>t; while(t--)
{ cin>>n;
n*=2; for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n); for(int i=0;i<n;i+=2)
{
swap(a[i],a[i+1]);
}
swap(a[0],a[n-1]); for(int i=0;i<n;i++) cout<<a[i]<<" ";
cout<<endl;
}
}
C1. Potions (Easy Version)
链接https://codeforces.com/contest/1526/problem/C1
题意:对于一堆物品,物品的权值有正有负,初始体力值为0,按顺序一个个考虑选或不选,如果权值为正,加体力,为负减体力,确保体力不为负的同时,选择最多的物品
思路:由于数据范围可以n^2,并且很像背包问题,所以简单版就考虑用dp做
f[i][j][k],表示第i个物品,在选了j个物品的情况下,第i个物品是选还是不选(0不选,1选)
对于状态的转移,可以从第i个物品的选择情况作为划分依据
如果不选,f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1])
如果选,就等价于考虑前i-1个物品的情况,所以
if(f[i-1][j-1][0]+x>=0)
f[i][j][1]=max(f[i][j][1],f[i-1][j-1][0]+x);
if(f[i-1][j-1][1]+x>=0)
f[i][j][1]=max(f[i][j][1],f[i-1][j-1][1]+x);
#include<iostream>#include<algorithm>#include<cstring>using namespace std;const int N=3000;typedef long long LL;
LL f[N][N][2];int n;int main(){ cin>>n; int res=0; memset(f,-0x3f,sizeof f);
f[0][0][1]=0;
f[0][0][0]=0; for(int i=1;i<=n;i++)
{
LL x; cin>>x; for(int j=0;j<=n;j++)
{ if(j>i) continue;
f[i][j][0]=max(f[i-1][j][1],f[i-1][j][0]); if(j-1>=0)
{ if(f[i-1][j-1][0]+x>=0)
{
f[i][j][1]=max(f[i][j][1],f[i-1][j-1][0]+x);
} if(f[i-1][j-1][1]+x>=0)
{
f[i][j][1]=max(f[i][j][1],f[i-1][j-1][1]+x);
}
}
}
} for(int i=n;i>=0;i--)
{ if(f[n][i][0]>=0||f[n][i][1]>=0)
{ cout<<i<<endl; break;
}
}
}C2. Potions (Hard Version)
题意一样,就是数据变成10^5
思路:由于数据范围之内在n或者nlogn解决,所以不再考虑dp,其实这道题用贪心就能解决,类似的贪心还有最长上升子序列的优化版本,以及icpc昆明站的L题https://ac.nowcoder.com/acm/contest/14055/L
对于这样的问题一般都线性的去考虑,用一个值now记录当前的大小,可以发现,如果当前now<0,如果我们仍是要选择当前的物品,那么是否可以将当前物品放入背包的同时,还能得到正确答案呢?
可以发现,如果背包中有权值比当前物品更小的,那么就一定可以用当前物品替换,并且结果一定不会比原本差,这就类似于最长上升子序列的优化版本。
#include <iostream>#include <algorithm>#include <queue>using namespace std;typedef long long LL;int n;
LL res;
LL now;
LL x;priority_queue<int,vector<int>,greater<int>>q;int main(int argc, char *argv[]) { int n; cin>>n; for(int i=0;i<n;i++)
{ cin>>x;
q.push(x);
now+=x;
res++; if(now<0)
{
now-=q.top();
q.pop();
res--;
}
}
cout<<res<<endl;
}来源https://www.cnblogs.com/Grantland/p/14829761.html