//题意:一个的工作时间是m分钟。 // 在特定的时间和咖啡 n a1,a2....an,, ai代表的是每个咖啡要在一天中对应的时间点喝掉 // 每一次喝咖啡的时间为1分钟 // 必须在一天中的ai时刻喝掉对应的咖啡 // 在两次喝咖啡中间要有d分钟休息时间,天与天之间时间大于d // 尽可能少的天数内将所有咖啡喝完,不只有一种解法 // input 输入 n(n杯咖啡), m(一天有m分钟工作时间), d(间隔时间) // a1,a2...an(第n杯咖啡要在一天中的第an时间点喝掉) //ouput 输出 最少的天数 // 每杯咖啡在第几天喝掉 //1.set<pair<int,int> >的用法 // //set默认的比较规则先按照first比较, //如果first相同,再按照second 比较。 //注意:定义的时候右边的两个>>要空一格。 //upper_bound(begin,end,i)用法是查找排好序的从begin开始到end结束大于i的数,二分查找方法 //lower_bound(begin,end,i)用法是查找排好序的从begin开始到end结束不大于i的数,二分查找方法 //set //本题用的upper_bound(make_pair(a[pos]+d,INF))后面的INF一定要加,现根据前面查找,然后根据后面查找,均二分 //本题用的lower_bound(make_pair(a[pos]+d+1,0))后面o也一定要加,现根据前面查找,然后根据后面查找,均二分 #include <stdio.h> #include <string.h> #include <set> #include <stdio.h> #include <iostream> using namespace std; const int MAX = 2e5 + 10; const int INF = 9e9 + 10; int a[MAX], ans[MAX]; set<pair<int,int> > ss; set<pair<int,int> > :: iterator it; int main(){ int n, m, d; int count = 0,pos; cin >> n >> m >> d; for( int i = 1; i <= n; i++ ) { scanf("%d",&a[i]); ss.insert(make_pair(a[i],i)); } while( !ss.empty() ) { count++; // cout<<ss.begin()->first<<" "<<ss.begin()->second<<endl; pos = ss.begin()->second; ans[pos] = count; ss.erase(ss.begin()); while(1){ // ss.upper_bound(make_pair(a[pos]+d,INF)) //这两都可以用 it = ss.lower_bound(make_pair(a[pos]+1+d,0)); if(it==ss.end()) break; pos = it->second; ans[pos] = count; ss.erase(it); } } printf("%d\n",count); for(int i = 1;i<=n;i++){ printf("%d%c",ans[i],i==n?'\n':' '); } return 0; }