建站教程的优点杭州seo中心

C. Light Switches

原题链接

题意：

房间的灯最初均为关闭状态，安装芯片后，它会每隔k分钟改变一次房间的灯光状态，即会打开灯光k分钟，关闭k分钟再打开，依次重复。
有n个房间，在不同时间安装芯片，最早什么时间可以使这些灯都在打开状态，如果不存在所有房间灯都打开的时刻·，则输出-1.

解题思路：

1.将所有时刻都排序，取最大时刻的亮灯区间
2.依次与数组中别的时刻的亮灯区间取交集
3.取交集时，我们应先将此时刻变换到接近区间的值，然后利用交集更新l,r
4.如果最终交际存在即l<r,则输出最大时刻，否则输出-1

解题代码：

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); 
#define endl '\n'
using namespace std;void solve() 
{int n,k;cin>>n>>k;int a[n];for(int i=0;i<n;i++){cin>>a[i];}sort(a,a+n);int l=a[n-1],r=a[n-1]+k-1;for(int i=0;i<n-1;i++){a[i]=((l-a[i])/(2*k))*(2*k)+a[i];if(a[i]+k<l)a[i]+=2*k;l=max(l,a[i]);r=min(r,a[i]+k-1);}if(l>r){cout<<"-1\n";return;}cout<<l<<endl;
}signed main() {IOSint T = 1;cin >> T;while (T--){solve();}return 0;
}