A. Benches
题意:公园一共有N个长椅,每个椅子上有Ai个人,后面会新来M个人,问你当M个人坐下以后人数最多的长椅上可以存在的最小人数和最大人数
题解:将每个长椅上的人数塞进一个优先队列,然后每次从优先队列里面取出人数最少的长椅坐一个人上去,最后得到的最大的长椅人数就是可能存在的最小值,而最大值直接就是人数最多的长椅人数加M
#include <bits/stdc++.h>
using namespace std;
int N,M,ans;
priority_queue<int>Q1;
priority_queue<int>Q2;
int main()
{
scanf("%d %d",&N,&M);
int v;
for(int i =1;i <= N;i++){
scanf("%d",&v);
Q1.push(v);
Q2.push(-v);
ans = max(ans,v);
}
for(int i = 1;i <= M;i++){
v = -Q2.top();Q2.pop();v++;
Q2.push(-v);
ans = max(v,ans);
}
printf("%d %d\n",ans,Q1.top()+M);
return 0;
}
B. Vitamins
题意:有N种药物,每一个的价格为ci,可以补充营养的种类为Si
题解:将每种药物最便宜的找出来,然后将所有药物组合计算一下
#include <bits/stdc++.h>
const int MAXN = 10000,INF = 1000000;
using namespace std;
int n,ans = INF;
map<string,int>mp;
int main()
{
int v;string s;
scanf("%d",&n);
mp["A"] = INF;
mp["B"] = INF;
mp["C"] = INF;
mp["AB"] = INF;
mp["BC"] = INF;
mp["AC"] = INF;
mp["ABC"] = INF;
for(int i = 1;i <= n;i++){
scanf("%d",&v);
cin>>s;
sort(s.begin(),s.end());
mp[s] = min(mp[s],v);
}
ans = min(ans,mp["A"]+mp["B"]+mp["C"]);
ans = min(ans,mp["AB"]+mp["C"]);
ans = min(ans,mp["AC"]+mp["B"]);
ans = min(ans,mp["BC"]+mp["A"]);
ans = min(ans,mp["AB"]+mp["BC"]);
ans = min(ans,mp["AC"]+mp["BC"]);
ans = min(ans,mp["AB"]+mp["AC"]);
ans = min(ans,mp["ABC"]);
if(ans == INF) printf("-1\n");
else printf("%d\n",ans);
return 0;
}
C. Array Product
题意:给你一个长度为N的数列,你可以选择将任意两个数相乘并保留其中一个,或者是在任何时间删除其中的一个数值(只能删除一次或者是不删除)
题意:模拟,用set将位置存储在一起,先将所有的0和正数乘到一起,如果有奇数个负数那就把最大的负数和0乘到一起然后删除,否则直接把0删除,注意:不存在正数的情况。我太菜了。。。代码好长
#include <bits/stdc++.h>
using namespace std;
#define ps push
#define mp make_pair
typedef pair<int,int> PII;
int n,suma,sumb,sumc;
PII it;
priority_queue<PII>a,b,c;
int main()
{
scanf("%d",&n);
int u,v;
for(int i = 1;i <= n;i++){
scanf("%d",&v);
if(v > 0) {
a.ps(mp(v,i));
suma++;
}
if(v == 0){
b.ps(mp(v,i));
sumb++;
}
if(v < 0){
c.ps(mp(v,i));
sumc++;
}
}
while(sumb > 1){ //留一个0
it = b.top();b.pop();sumb--;u = it.second;
it = b.top();v = it.second;
printf("1 %d %d\n",u,v);
}
if(sumb == 1 && suma == 0 && sumc == 0) return 0;
while(suma > 1){//留一个正数
it = a.top();a.pop();suma--;u = it.second;
it = a.top();v = it.second;
printf("1 %d %d\n",u,v);
}
if(suma == 0 && sumc == 1){
it = b.top();u = it.second;
it = c.top();v = it.second;
printf("1 %d %d\n",u,v);
return 0;
}
if(sumb && sumc & 1){
it = b.top();b.pop();sumb--;u = it.second;
it = c.top();c.pop();sumc--;v = it.second;
printf("1 %d %d\n",u,v);
printf("2 %d\n",v);
}
else if(sumb && !(sumc & 1)){
it = b.top();b.pop();sumb--;v = it.second;
printf("2 %d\n",v);
}
else if(sumb == 0 && sumc & 1){
it = c.top();c.pop();sumc--;v = it.second;
printf("2 %d\n",v);
}
if(suma && sumc){
it = a.top();a.pop();suma--;u = it.second;
it = c.top();v = it.second;
printf("1 %d %d\n",u,v);
}
while(sumc > 1){
it = c.top();c.pop();sumc--;u = it.second;
it = c.top();v = it.second;
printf("1 %d %d\n",u,v);
}
return 0;
}
D. Petya and Array
题意:给你n个数,问有多少个区间的和的值小于t
题解:
sum[i]代表前i个数的和
那么题目表达为:存在多少个0<=k<i使得sum[i]-t<sum[k]
需要注意的是上面的K是从0开始求的,定义sum[0]=0;而sum[i]-sum[0]=sum[i];这样的意义在于将当前点前缀和统计进去
所以直接按权值建线段树统计使上式成立的K的数量,但是因为sum可能很大,故需要离散化
#include <bits/stdc++.h>
const long long MAXN = 1000000;
using namespace std;
int x;
long long n,t,top,ans,a;
long long sum[MAXN],Hash[MAXN],data[MAXN],tmp;
inline long long read(){
long long x = 0,f = 1;char ch = getchar();
while(ch < '0' || '9' < ch){if(ch == '-')f = -1;ch = getchar();}
while('0' <= ch&& ch <='9'){x = x * 10 + ch - '0'; ch = getchar();}
return x*f;
}
inline void init()
{
n = read();t = read();
for(int i = 1;i <= n;i++) data[i] = read();
for(int i = 1;i <= n;i++){
Hash[i] = Hash[i-1] + data[i];
}
sort(Hash+1,Hash+n+2);
top = unique(Hash+1,Hash+n+2) - Hash;
}
void update(int o,int L,int R){
if(L == R) {
sum[o]++;
return;
}
int M = L + R >> 1;
if(x <= M) update(o<<1,L,M);
else update(o<<1|1,M+1,R);
sum[o] = sum[o<<1] + sum[o<<1|1];
}
void query(int o,int L,int R){
if(L == R) {
tmp += sum[o];
return;
}
int M = L + R >> 1;
if(x <= M) {
tmp += sum[o<<1|1];
query(o<<1,L,M);
}
else query(o<<1|1,M+1,R);
}
inline void solve()
{
top--;
x = lower_bound(Hash+1,Hash+top+1,0) - Hash;
update(1,1,top);
for(int i = 1;i <= n;i++)
{
a += data[i];
x = lower_bound(Hash+1,Hash+top+1,a-t+1) - Hash;
if(x > top){x = lower_bound(Hash+1,Hash+top+1,a) - Hash;update(1,1,top);continue;}
tmp = 0;query(1,1,top);
ans += tmp;
x = lower_bound(Hash+1,Hash+top+1,a) - Hash;
update(1,1,top);
}
}
int main()
{
init();
solve();
printf("%lld\n",ans);
return 0;
}
tql
榕榕姐别闹。
希望你可以走得更远!