个人网站备案网址导航,晨光科技+网站建设,汤姆叔叔官方网站建设,单页网站有后台Problem - A - Codeforces
思路#xff1a;
按照等级排序#xff0c;维护同等级最大评分#xff0c;每个等级的总评分至少比其第前一个等级的最大评分大1分
吐槽#xff1a;
思路不难#xff0c;但坑好多#xff0c;感觉全踩了一遍
坑#xff1a;#xff08;按解决…Problem - A - Codeforces
思路
按照等级排序维护同等级最大评分每个等级的总评分至少比其第前一个等级的最大评分大1分
吐槽
思路不难但坑好多感觉全踩了一遍
坑按解决先后排序
要维护同等级的最大值并且与前一等级的排序不能只根据排完序后前一个的总评分进行判断
储存 -1 所在的位置代替遍历查找用空间换时间
题目要求按输入顺序输出各个比赛的评分不要进行两次排序不要格外用上离散化充分利用好下标
不要用pairint,vectorint 类型的数组排序用pair对应起等级和下标就行
更新前驱不受是否需要填值影响
AC代码
#includebits/stdc.h
using namespace std;#define int long longbool cmp(pairint,int a,pairint,int b){return a.firstb.first;
} //pairint,int装等级,下标将等级小的排在前面int n,m,k;
int x; int cc;void solve(){cinnmk;pairint,int grade[n]; //装等级,下标将每个竞赛的等级与其下标对应起来vectorint score[n],location[n]; //储存每个竞赛的评分、其-1元素在score[]的位置mapint,int mx; //储存每个等级评分和的最大值for(int i0;in;i){cingrade[i].first; grade[i].secondi; //输入等级对应其下标int sum0 , cnt0; //用于统计该竞赛当前评分和、-1元素的数量score[i].push_back(0); //留出score[]的第一个位置用于存放该竞赛当前评分和for(int j1;jm;j){cinx;score[i].push_back(x);if(x-1){cnt; //统计-1数量location[i].push_back(j); //储存-1位置}else{sumx; //统计评分和}}mx[grade[i].first] max(mx[grade[i].first],sum); //更新当前等级竞赛的最大评分和score[i][0]sum; //0号位存放评分和score[i].push_back(cnt); //m1号位存放-1的数量}sort(grade,graden); //按等级进行排序int front 0; //记录 当前等级的 前一个等级 的 下标for(int i1;in;i){if(grade[i].first grade[0].first) continue; //跳过最低等级的竞赛int should max(score[grade[i].second][0],mx[grade[front].first]1); //该竞赛的最小评分和应为max该竞赛当前评分和前一等级竞赛最大评分和1int difference should-score[grade[i].second][0]; //记录should 与 当前竞赛评分和的差if(difference){ //如果差不为0意味这要填分到-1所在的位置if(score[grade[i].second][m1]*kdifference){coutNo\n; return;} //如果-1的个数*k 不足以填补 差 则输出No直接判出for(int j0;jlocation[grade[i].second].size() difference0;j){ //调出-1元素的位置按差填值填完结束cc location[grade[i].second][j];if(differencek){score[grade[i].second][cc]k; score[grade[i].second][0]k; difference-k; //更新-1处的值更新该竞赛评分和更新差的值}else{score[grade[i].second][cc]difference; score[grade[i].second][0]difference; difference-difference; //更新-1处的值更新该竞赛评分和更新差的值}}mx[grade[i].first] max(mx[grade[i].first],score[grade[i].second][0]); //更新当前等级最大评分和}if(grade[i].first ! grade[i1].first) front i; //如果当前竞赛的等级与其后面一个竞赛等级不同则更新front将当前竞赛的等级作为 前一个等级 因为grade[]已经排序此行必须放在if(difference){}之外就算当前等级竞赛的difference都为0也必须更新front不然到下一个等级的竞赛算should时会得到错误的值}coutYes\n; //一切安好就输出Yes平凡即是喜乐?for(int i0;in;i){for(int j1;jm;j){if(score[i][j]-1) cout0 ; //还是-1的位置就输出0else coutscore[i][j] ;}cout\n;}
}signed main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t;cint;while(t--){solve();}return 0;
}
