当前位置: 代码迷 >> 综合 >> Codeforces #325 Div2 C Gennady the Dentist(模拟、细节)
  详细解决方案

Codeforces #325 Div2 C Gennady the Dentist(模拟、细节)

热度:91   发布时间:2023-12-08 10:55:25.0

题目链接:
Codeforces #325 Div2 C Gennady the Dentist
题意:
有n个孩子要去看牙医,每个孩子有三个属性v,d,p,看牙医的孩子会对后面正在排队的孩子产生影响,
当一个孩子的p小于0时,也会对后面正在排队的孩子产生影响,并提前离开队伍。
问最终会有哪些孩子成功看了牙医?
分析:
模拟。一开始写了下面第一个模拟,感觉没啥问题,可是总是WA,百思不得其解,后来换了个写法,感觉没啥区别
(需要注意开long long)就AC了,再后来终于想通了问题出在哪里了!!!

/* 错误分析: 在仅用v[i]更新i后面的p[j]时候,需要判断p[j]是否已经小于0,如果不使用在j之前的已经leave的children的 d的信息,那么有可能因为没使用d使得p[j]本该是负数而没处理成负数,就不对了呀! */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
using namespace std;
const int MAX_N=4010;int n;
long long d[MAX_N],p[MAX_N],v[MAX_N];
int cure[MAX_N];int main()
{freopen("C.in","r",stdin);while(~scanf("%d",&n)){int ans=0;for(int i=0;i<n;i++){scanf("%I64d%I64d%I64d",&v[i],&d[i],&p[i]);}for(int i=0;i<n;i++){if(p[i]>=0){ //curecure[ans++]=i+1;for(int j=i+1;j<n;j++){if(p[j]<0) continue;p[j]-=v[i];v[i]--;if(v[i]==0) break;}}else { //escapefor(int j=i+1;j<n;j++){if(p[j]<0) continue;p[j]-=d[i];}}}printf("%d\n",ans);for(int i=0;i<ans;i++){printf("%d ",cure[i]);}printf("\n");}return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
using namespace std;
const int MAX_N=4010;int n;
long long d[MAX_N],p[MAX_N],v[MAX_N];
int cure[MAX_N];int main()
{freopen("C.in","r",stdin);while(~scanf("%d",&n)){int ans=0;for(int i=0;i<n;i++){scanf("%I64d%I64d%I64d",&v[i],&d[i],&p[i]);}for(int i=0;i<n;i++){if(p[i]<0) continue;cure[ans++]=i+1;long long cur=v[i],extra=0;for(int j=i+1;j<n;j++){if(p[j]<0) continue;p[j]-=(cur+extra);if(p[j]<0) extra += d[j];if(cur>0) cur--;}}printf("%d\n",ans);for(int i=0;i<ans;i++){printf("%d ",cure[i]);}printf("\n");}return 0;
}
  相关解决方案